Big O Notation

What is Big O?

"Big O" is a notation used to measure the efficiency of an algorithm in terms of execution time or memory usage, also known as complexity.

How does it work?

In simple terms, Big O describes how the execution time (or memory usage) grows as the input data size (represented by the letter n) increases.

Main complexity classes

Constant Complexity

• Representation: O(1)
• The algorithm's cost is independent of the size of n. Instructions are executed a fixed number of times.

// Regardless of the size of the array, 
// the instruction is executed only once
public static int example1(int[] array) {
    return array[array.length / 2];
}

Linear Complexity

• Representation: O(n)
• The algorithm's cost grows linearly with the input size. Each input element needs to be processed once.

// This algorithm iterates through each element of the array once, summing the values.
public static int example2(int[] array) {
    int sum = 0;
    for (int i = 0; i < array.length; i++) {
        sum += array[i];
    }
    return sum;
}

Quadratic Complexity

• Representation: O(n²)
• The algorithm's cost increases quadratically with the size of n. It typically occurs when there are two nested loops.

// This algorithm implements a sorting method, the Bubble Sort
public static void bubbleSort(int[] array) {
    int temp;
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

Logarithmic Complexity

• Representation: O(log n)
• The algorithm's cost grows logarithmically with the size of n. It is common in search algorithms or divide and conquer algorithms.

// This algorithm performs a binary search on a SORTED array
public static int example4(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (array[middle] == key) {
            return middle;
        }
        if (array[middle] < key) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return -1;
}

Complexity and Optimization

The following graph demonstrates, in terms of time and memory efficiency, which complexities perform better as input parameters tend to infinity:

_{^{Graph: https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/}}