Understanding Big O Notation

Big O Notation is a mathematical notation used to describe the upper bound of an algorithm's runtime or space requirements in terms of input size. It provides a high-level understanding of the algorithm's efficiency.

Constant Time Complexity

An algorithm has constant time complexity, O(1), if its runtime does not change regardless of the input size. Accessing an element in an array by index is a common example.

int getFirstElement(int[] array) {
    return array[0];
}
      

Linear Time Complexity

An algorithm has linear time complexity, O(n), if its runtime grows linearly with the input size. Traversing an array to find a maximum element is a typical example.

int findMax(int[] array) {
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    return max;
}
      

Logarithmic Time Complexity

An algorithm has logarithmic time complexity, O(log n), when its runtime increases logarithmically with the input size. Binary search is a classic example.

int binarySearch(int[] array, int target) {
    int left = 0, right = array.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] == target) return mid;
        if (array[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
      

Quadratic Time Complexity

An algorithm has quadratic time complexity, O(n^2), when its runtime is proportional to the square of the input size. Bubble sort is a well-known example.

void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}
      

Exponential Time Complexity

An algorithm has exponential time complexity, O(2^n), when its runtime doubles with each additional input element. The recursive calculation of Fibonacci numbers is an example.

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}