[[Big O notation]]

[[Best, average, worst cases]]

Time and space complexity are used to evaluate the efficiency of algorithms in terms of performance (time) and memory usage (space).

1. Common Time Complexities:

• O(1) - Constant Time: The algorithm takes the same time, regardless of the input size. Example: Accessing an element in an array by index.
• O(log n) - Logarithmic Time: The time grows logarithmically with the input size, usually seen in divide-and-conquer algorithms like binary search.
• O(n) - Linear Time: The time grows linearly with the input size. Example: Traversing an array.
• O(n log n): Seen in efficient sorting algorithms like merge sort and quicksort.
• O(n²) - Quadratic Time: The time grows quadratically with the input size. Example: Nested loops, such as in bubble sort or selection sort.
• O(2^n) - Exponential Time: The time doubles with each additional element in the input, usually seen in recursive problems like the Fibonacci sequence (without memoization).
• O(n!) - Factorial Time: The time grows factorially, typical in algorithms that generate all permutations or combinations (like the traveling salesman problem).

public class SumArray {
    public static int sumArray(int[] arr) {
        int sum = 0;           // O(1) - Constant time operation
        for (int i = 0; i < arr.length; i++) {   // O(n) - Loop runs n times
            sum += arr[i];     // O(1) - Constant time for addition
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(sumArray(arr));  // Output: 15
    }
}

2. space complexity

Space complexity refers to the amount of memory an algorithm uses during its execution.It considers both the input space (memory required for input) and auxiliary space (memory used for variables and data structures).

Common Space Complexities:

• O(1) - Constant Space: The algorithm uses a fixed amount of memory regardless of input size. Example: Swapping two variables.
• O(n) - Linear Space: The memory usage grows linearly with the input size. Example: Storing results in an array.
• O(n²): The memory grows quadratically, often seen in 2D matrices or dynamic programming tables.

public class SpaceExample {
    public static int[] createArray(int n) {
        int[] arr = new int[n];    // O(n) - Space allocated for array
        for (int i = 0; i < n; i++) {
            arr[i] = i;            // O(1) - Assigning value takes constant space
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] result = createArray(5);  // Output: [0, 1, 2, 3, 4]
    }
}

Here’s a tabular summary of the time complexity for common operations on various data structures:

Quick Definitions:

• V: Number of vertices (for graphs)
• E: Number of edges (for graphs)
• n: Number of elements in the data structure
• m: Length of the string/key (for tries)

Important Observations:

• Arrays offer fast access (O(1)) but are slow for inserts/deletes (O(n)).
• Linked Lists allow fast insertions/deletions at the ends but slow access and search.
• HashMaps are fast on average for all operations (O(1)) but degrade with poor hashing to O(n).
• Balanced trees like AVL and Red-Black Trees ensure O(log n) performance for all basic operations.
• Heaps are perfect for extracting the min/max in logarithmic time.
• Graphs have different time complexities based on representation: adjacency list is better for sparse graphs, adjacency matrix for dense graphs.

This table helps you get a bird’s-eye view of different data structures and their performance characteristics!