Time and Space Complexity

To evaluate the efficiency of an algorithm, we look at its Time Complexity and Space Complexity. The objective is generally to minimize both.

Big O Notation

Big O Notation describes the upper bound of the time or space an algorithm requires, relative to the size of the input (n). It deals with the worst-case scenario.

Common Complexities

(From fastest/most efficient to slowest/least efficient)

Complexity	Name	Example
O(1)	Constant	Accessing an array element by index.
O(log n)	Logarithmic	Binary Search.
O(n)	Linear	Traversing an array.
O(n log n)	Linearithmic	Merge Sort, Quick Sort.
O(n²)	Quadratic	Bubble Sort, Selection Sort.

Time Complexity Example in Java

If an algorithm runs independent of the input size, it's O(1). If it runs in a loop relative to n, it's O(n).

// O(1) Constant Time
public void printFirstElement(int[] arr) {
    System.out.println(arr[0]);
}

// O(n) Linear Time
public void printAllElements(int[] arr) {
    for (int num : arr) {
        System.out.println(num);
    }
}

// O(n^2) Quadratic Time
public void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}

Space Complexity

Space complexity is the total memory space required by the program for its execution as a function of the input size. It encompasses both Auxiliary Space (extra temporary space) and the space required by inputs.

// O(1) Space - Only a few variables allocated regardless of input size
public int sum(int[] arr) {
    int total = 0; 
    for(int n : arr) {
        total += n;
    }
    return total;
}

// O(n) Space - Returning a new array proportional to input size
public int[] duplicate(int[] arr) {
    int[] newArr = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}