Big O Notation

What Is Big O Notation?

Big O notation describes how an algorithm's runtime or memory usage grows as input size increases.

It provides a high-level measure of efficiency in both time and space complexity.

Common Big O Notations

Notation	Description	Example Algorithm
O(1)	Constant time: takes the same number of steps regardless of input size.	Access a value at a known position or flip a single flag. The work is the same whether the data set has 10 or 10 million items.
O(log n)	Logarithmic time: progress comes from repeatedly shrinking the problem by a fixed fraction.	You cut the remaining possibilities down dramatically at each step. Each stage leaves a much smaller set to consider. Doubling the input typically adds only about one extra step.
O(n)	Linear time: work grows in direct proportion to the input size.	You examine each item once from start to finish. Time increases one-for-one with the number of items. Doubling the input roughly doubles the work.
O(n log n)	Linearithmic time: near-linear work repeated over a logarithmic number of stages.	The process runs through about log n phases, and each phase touches most items. Total effort is the sum of those near-linear passes. It grows faster than linear but far slower than quadratic.
O(n²)	Quadratic time: work grows with the square of the input, often due to nested iteration.	For each item, you perform another pass over many or all items, creating many pairwise checks. Doubling the input can quadruple the time. Fine for small inputs, but it scales poorly.
O(2ⁿ)	Exponential time: work doubles with each additional element; growth is explosive.	You must evaluate an ever-expanding set of possibilities as the input grows. Each new element can double the number of cases to consider. Practical only for very small inputs.

Big O Graph

Example: Analysing Algorithm Efficiency

O(1): Array Access

arr = [5, 10, 15, 20]
index = 2  # chosen index
value = arr[index]
print("Accessed value:", value)
print(f"State: index={index}, comparisons=0, swaps=0")

int[] arr = {5, 10, 15, 20};
int index = 2;  // chosen index
int value = arr[index];
System.out.println("Accessed value: " + value);
System.out.println("State: index=" + index + ", comparisons=0, swaps=0");

O(log n): Binary Search

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    comparisons = 0
    while left <= right:
        comparisons += 1
        mid = left + (right - left) // 2
        if arr[mid] == target:
            print("Comparisons:", comparisons)
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    print("Comparisons:", comparisons)
    return -1

numbers = [1, 3, 5, 7, 9]
binary_search(numbers, 7)  # prints comparisons count

public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int comparisons = 0;
    while (left <= right) {
        comparisons++;
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            System.out.println("Comparisons: " + comparisons);
            return mid;
        }
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    System.out.println("Comparisons: " + comparisons);
    return -1;
}

// Example usage
int[] numbers = {1, 3, 5, 7, 9};
binarySearch(numbers, 7);  // prints comparisons count

O(n): Linear Search

def linear_search(arr, target):
    comparisons = 0
    for i in range(len(arr)):
        comparisons += 1
        if arr[i] == target:
            print(f"Comparisons: {comparisons}")
            return i
    print(f"Comparisons: {comparisons}")
    return -1

numbers = [1, 3, 5, 7, 9]
linear_search(numbers, 7)  # prints comparisons count

public static int linearSearch(int[] arr, int target) {
    int comps = 0;
    for (int i = 0; i < arr.length; i++) {
        comps++;
        if (arr[i] == target) {
            System.out.println("Comparisons: " + comps);
            return i;
        }
    }
    System.out.println("Comparisons: " + comps);
    return -1;
}

// Example usage
int[] numbers = {1, 3, 5, 7, 9};
linearSearch(numbers, 7);

O(n log n): Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr, 0, 0  # arr, comparisons, swaps
    mid = len(arr) // 2
    left, c1, s1 = merge_sort(arr[:mid])
    right, c2, s2 = merge_sort(arr[mid:])
    merged, c3, s3 = merge(left, right)
    return merged, c1 + c2 + c3, s1 + s2 + s3

def merge(left, right):
    i = j = 0
    comparisons = swaps = 0
    result = []
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1; swaps += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result, comparisons, swaps

arr = [5, 2, 9, 1, 5, 6]
sorted_arr, comps, swaps = merge_sort(arr)
print("Sorted:", sorted_arr)
print(f"Comparisons: {comps}, Swaps: {swaps}")

static class Result { int[] arr; int comps; int swaps;
    Result(int[] a, int c, int s){ arr=a; comps=c; swaps=s; } }

public static Result mergeSort(int[] arr){
    if (arr.length <= 1) return new Result(arr.clone(), 0, 0);
    int mid = arr.length / 2;
    int[] left = java.util.Arrays.copyOfRange(arr, 0, mid);
    int[] right = java.util.Arrays.copyOfRange(arr, mid, arr.length);
    Result L = mergeSort(left), R = mergeSort(right);
    Result M = merge(L.arr, R.arr);
    return new Result(M.arr, L.comps + R.comps + M.comps, L.swaps + R.swaps + M.swaps);
}

private static Result merge(int[] left, int[] right){
    int i=0, j=0, comps=0, swaps=0;
    int[] out = new int[left.length + right.length];
    int k = 0;
    while (i < left.length && j < right.length){
        comps++;
        if (left[i] <= right[j]) out[k++] = left[i++];
        else { out[k++] = right[j++]; swaps++; }
    }
    while (i < left.length) out[k++] = left[i++];
    while (j < right.length) out[k++] = right[j++];
    return new Result(out, comps, swaps);
}

// Example usage
int[] arr = {5, 2, 9, 1, 5, 6};
Result res = mergeSort(arr);
System.out.println("Sorted: " + java.util.Arrays.toString(res.arr));
System.out.println("Comparisons: " + res.comps + ", Swaps: " + res.swaps);

O(n²): Bubble Sort

def bubble_sort(arr):
    n = len(arr)
    comps = swaps = 0
    for i in range(n - 1):
        for j in range(n - i - 1):
            comps += 1
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swaps += 1
    print(f"Comparisons: {comps}, Swaps: {swaps}")

a = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(a)

public class BubbleSortStats {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        int comps = 0, swaps = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                comps++;
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    swaps++;
                }
            }
        }
        System.out.println("Comparisons: " + comps + ", Swaps: " + swaps);
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
    }
}

O(2ⁿ): Recursive Fibonacci

calls = 0

def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

value = fib(5)
print(f"Fibonacci(5) = {value}, Calls = {calls}")

public class FibStats {
    static int calls = 0;

    public static int fib(int n) {
        calls++;
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        calls = 0;
        int value = fib(5);
        System.out.println("Fibonacci(5) = " + value + ", Calls = " + calls);
    }
}

Quick Wins for Complexity Identification

No Loops: Code without any loops (e.g. a single calculation or direct array access) typically runs in O(1) time.
Single Loop: A single for or while loop over the input implies O(n) time, where performance grows linearly with input size.
Nested Loops: Loops inside loops (e.g. two nested for loops over the same input) usually indicate O(n²) time due to pairwise element processing.

Choosing the Right Algorithm

Hash Lookups (O(1)): Use dictionaries or hash maps for constant-time access.
Searching Sorted Data (O(log n)): Use binary search on sorted arrays or lists.
Efficient Sorting (O(n log n)): Prefer merge sort for large datasets.
Minimize Quadratic Algorithms (O(n²)): Avoid nested loops on large inputs.
Beware Exponential (O(2ⁿ)): Use dynamic programming or memoization for recursive problems.

Avoiding Common Mistakes

Scalability: Test with increasing data sizes to observe growth.
Nested Loops: Replace nested loops with divide-and-conquer when possible.
Space–Time Trade-offs: Balance memory usage and runtime efficiency.

Key Takeaways

Big O notation quantifies algorithm efficiency as input scales.
Time complexities range from O(1) to O(2ⁿ) and beyond.
Instrumentation (counters for comparisons/swaps) helps empirically measure performance.
Choose algorithms based on data size, growth behavior, and resource constraints.