Big O Notation

Introduction

Big O notation is a mathematical framework used to describe the upper bound of an algorithm's time or space complexity as input size grows. It provides a standardized way to compare algorithms, reason about scalability, and make informed engineering decisions — skills essential for system design interviews, performance tuning, and writing production-grade code.

Core Concepts

What Big O Really Measures

Big O notation describes the asymptotic behavior of a function — how it behaves as the input size n approaches infinity. It strips away constants and lower-order terms to focus on the dominant growth factor. When we say an algorithm is O(n²), we mean that in the worst case, the number of operations grows proportionally to the square of the input size.

Key principles:

• Worst-case analysis: Big O typically describes the upper bound (worst case)
• Drop constants: O(2n) simplifies to O(n)
• Drop non-dominant terms: O(n² + n) simplifies to O(n²)
• Input matters: Different inputs may have different variables (O(n * m) for two arrays)

Common Complexity Classes

Notation	Name	Example	n=1,000 Operations
O(1)	Constant	HashMap lookup	1
O(log n)	Logarithmic	Binary search	~10
O(n)	Linear	Array scan	1,000
O(n log n)	Linearithmic	Merge sort	~10,000
O(n²)	Quadratic	Nested loops	1,000,000
O(2ⁿ)	Exponential	Power set	2^1000 (infeasible)
O(n!)	Factorial	Permutations	Astronomically large

Big O vs Big Theta vs Big Omega

• Big O (O): Upper bound — the algorithm will perform at most this many operations
• Big Omega (Ω): Lower bound — the algorithm will perform at least this many operations
• Big Theta (Θ): Tight bound — the algorithm performs exactly at this rate asymptotically

In practice, engineers almost always use Big O, and often informally use it to mean the tight bound.

Space Complexity

Big O applies equally to memory usage. Space complexity counts the additional memory an algorithm needs relative to input size, excluding the input itself (auxiliary space).

O(1) — Constant Time

The algorithm takes the same time regardless of input size.

import java.util.HashMap;
import java.util.Map;

public class ConstantTimeExample {

    // O(1) time, O(1) space
    public static int getFirstElement(int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("Array must not be empty");
        }
        return array[0]; // Direct index access — always one operation
    }

    // O(1) amortized time for HashMap operations
    public static void hashMapOperations() {
        Map<String, Integer> cache = new HashMap<>();
        
        cache.put("users", 42);       // O(1) average
        int value = cache.get("users"); // O(1) average
        boolean exists = cache.containsKey("users"); // O(1) average
        
        System.out.println("Value: " + value + ", Exists: " + exists);
    }

    public static void main(String[] args) {
        int[] data = {10, 20, 30, 40, 50};
        System.out.println("First element: " + getFirstElement(data));
        hashMapOperations();
    }
}

O(log n) — Logarithmic Time

Each step halves the remaining work. Binary search is the classic example.

public class LogarithmicTimeExample {

    // O(log n) time, O(1) space (iterative)
    public static int binarySearch(int[] sortedArray, int target) {
        int left = 0;
        int right = sortedArray.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // Avoids integer overflow

            if (sortedArray[mid] == target) {
                return mid;
            } else if (sortedArray[mid] < target) {
                left = mid + 1;  // Eliminate left half
            } else {
                right = mid - 1; // Eliminate right half
            }
        }

        return -1; // Not found
    }

    // O(log n) time, O(log n) space (recursive — stack frames)
    public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
        if (left > right) return -1;

        int mid = left + (right - left) / 2;

        if (arr[mid] == target) return mid;
        if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
        return binarySearchRecursive(arr, target, left, mid - 1);
    }

    public static void main(String[] args) {
        int[] data = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int target = 23;

        int index = binarySearch(data, target);
        System.out.println("Iterative — Found " + target + " at index: " + index);

        int indexRec = binarySearchRecursive(data, target, 0, data.length - 1);
        System.out.println("Recursive — Found " + target + " at index: " + indexRec);
    }
}

O(n) — Linear Time

Work scales directly with input size. Every element is visited once.

public class LinearTimeExample {

    // O(n) time, O(1) space
    public static int findMax(int[] array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException("Array must not be empty");
        }

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

    // O(n) time, O(n) space — two-sum with HashMap
    public static int[] twoSum(int[] nums, int target) {
        java.util.Map<Integer, Integer> seen = new java.util.HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[]{seen.get(complement), i};
            }
            seen.put(nums[i], i);
        }

        throw new IllegalArgumentException("No two-sum solution found");
    }

    public static void main(String[] args) {
        int[] data = {3, 7, 1, 9, 4, 6};
        System.out.println("Max: " + findMax(data));

        int[] result = twoSum(new int[]{2, 7, 11, 15}, 9);
        System.out.println("Two Sum indices: [" + result[0] + ", " + result[1] + "]");
    }
}

O(n log n) — Linearithmic Time

The gold standard for comparison-based sorting. Merge sort divides the array in half (log n) and merges all elements at each level (n).

import java.util.Arrays;

public class LinearithmicTimeExample {

    // O(n log n) time, O(n) space
    public static void mergeSort(int[] array, int left, int right) {
        if (left >= right) return;

        int mid = left + (right - left) / 2;
        mergeSort(array, left, mid);        // Sort left half
        mergeSort(array, mid + 1, right);   // Sort right half
        merge(array, left, mid, right);     // Merge halves
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) temp[k++] = array[i++];
        while (j <= right) temp[k++] = array[j++];

        System.arraycopy(temp, 0, array, left, temp.length);
    }

    public static void main(String[] args) {
        int[] data = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Before: " + Arrays.toString(data));
        mergeSort(data, 0, data.length - 1);
        System.out.println("After:  " + Arrays.toString(data));
    }
}

O(n²) — Quadratic Time

Nested iteration over the same collection. Performance degrades rapidly.

import java.util.Arrays;

public class QuadraticTimeExample {

    // O(n²) time, O(1) space — Bubble Sort
    public static void bubbleSort(int[] array) {
        int n = array.length;
        boolean swapped;

        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            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;
                    swapped = true;
                }
            }
            if (!swapped) break; // Optimization: stop if already sorted
        }
    }

    // O(n²) brute force two-sum (contrast with O(n) HashMap approach)
    public static int[] twoSumBruteForce(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("No solution");
    }

    public static void main(String[] args) {
        int[] data = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Before: " + Arrays.toString(data));
        bubbleSort(data);
        System.out.println("After:  " + Arrays.toString(data));
    }
}

O(2ⁿ) — Exponential Time

Common in recursive algorithms without memoization. Each level doubles the work.

import java.util.HashMap;
import java.util.Map;

public class ExponentialTimeExample {

    // O(2ⁿ) time, O(n) space — naive Fibonacci
    public static long fibNaive(int n) {
        if (n <= 1) return n;
        return fibNaive(n - 1) + fibNaive(n - 2);
    }

    // O(n) time, O(n) space — memoized Fibonacci
    private static Map<Integer, Long> memo = new HashMap<>();

    public static long fibMemoized(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);

        long result = fibMemoized(n - 1) + fibMemoized(n - 2);
        memo.put(n, result);
        return result;
    }

    // O(n) time, O(1) space — iterative Fibonacci
    public static long fibIterative(int n) {
        if (n <= 1) return n;
        long prev = 0, curr = 1;
        for (int i = 2; i <= n; i++) {
            long next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }

    public static void main(String[] args) {
        int n = 40;

        long start = System.nanoTime();
        long result1 = fibNaive(n);
        long naiveTime = System.nanoTime() - start;

        start = System.nanoTime();
        long result2 = fibMemoized(n);
        long memoTime = System.nanoTime() - start;

        start = System.nanoTime();
        long result3 = fibIterative(n);
        long iterTime = System.nanoTime() - start;

        System.out.printf("Naive    fib(%d) = %d  [%d ms]%n", n, result1, naiveTime / 1_000_000);
        System.out.printf("Memoized fib(%d) = %d  [%d ms]%n", n, result2, memoTime / 1_000_000);
        System.out.printf("Iterative fib(%d) = %d [%d ms]%n", n, result3, iterTime / 1_000_000);
    }
}

Note: The red nodes represent redundant calculations — fib(3) is computed twice, fib(2) three times. Memoization eliminates this waste.

Amortized Analysis

Some operations are expensive occasionally but cheap on average. Java's ArrayList.add() is O(1) amortized: most insertions are O(1), but when the internal array must resize, that single operation is O(n). Over n insertions, total work is still O(n), so each is O(1) amortized.

Analyzing Complex Algorithms

Multi-Variable Complexity

When algorithms work with multiple inputs, each gets its own variable:

public class MultiVariableExample {

    // O(n * m) time — where n = rows, m = cols
    public static int[][] createMatrix(int rows, int cols) {
        int[][] matrix = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = i * cols + j;
            }
        }
        return matrix;
    }

    // O(a + b) time — sequential iteration of two different collections
    public static void processCollections(int[] arrayA, int[] arrayB) {
        for (int val : arrayA) {  // O(a)
            System.out.print(val + " ");
        }
        for (int val : arrayB) {  // O(b)
            System.out.print(val + " ");
        }
    }

    // O(a * b) time — nested iteration of two different collections
    public static void crossProduct(int[] arrayA, int[] arrayB) {
        for (int a : arrayA) {       // O(a)
            for (int b : arrayB) {   // O(b)
                System.out.print("(" + a + "," + b + ") ");
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = createMatrix(3, 4);
        for (int[] row : matrix) {
            System.out.println(java.util.Arrays.toString(row));
        }
    }
}

Complexity Decision Flowchart

Data Structure Complexity Reference

Practical Benchmarking in Java

import java.util.*;

public class ComplexityBenchmark {

    @FunctionalInterface
    interface AlgorithmUnderTest {
        void run(int[] data);
    }

    public static long benchmark(AlgorithmUnderTest algorithm, int[] data, int runs) {
        // Warm-up
        for (int i = 0; i < 3; i++) {
            algorithm.run(data.clone());
        }

        long totalNanos = 0;
        for (int i = 0; i < runs; i++) {
            int[] copy = data.clone();
            long start = System.nanoTime();
            algorithm.run(copy);
            totalNanos += System.nanoTime() - start;
        }

        return totalNanos / runs;
    }

    public static void main(String[] args) {
        int[] sizes = {1_000, 5_000, 10_000, 50_000, 100_000};
        Random random = new Random(42);

        System.out.printf("%-10s %-18s %-18s%n", "Size", "Bubble Sort (ns)", "Arrays.sort (ns)");
        System.out.println("=".repeat(50));

        for (int size : sizes) {
            int[] data = random.ints(size, 0, size * 10).toArray();

            // Only benchmark bubble sort for small sizes
            long bubbleTime = size <= 50_000
                    ? benchmark(arr -> {
                        for (int i = 0; i < arr.length - 1; i++)
                            for (int j = 0; j < arr.length - i - 1; j++)
                                if (arr[j] > arr[j + 1]) {
                                    int t = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = t;
                                }
                    }, data, 3)
                    : -1;

            long jdkSortTime = benchmark(Arrays::sort, data, 10);

            System.out.printf("%-10d %-18s %-18d%n",
                    size,
                    bubbleTime >= 0 ? String.valueOf(bubbleTime) : "SKIPPED",
                    jdkSortTime);
        }
    }
}

Space-Time Tradeoff Patterns

Best Practices

1. Identify the dominant term: In O(n² + n log n + n), the answer is O(n²) — always focus on the fastest-growing term.
2. Consider all cases: Best, average, and worst case can differ significantly — quicksort is O(n log n) average but O(n²) worst case.
3. Account for hidden costs: String concatenation in a loop creates new strings each time — s += char in a loop is O(n²), not O(n).
4. Choose the right data structure first: Switching from a List to a HashMap can reduce lookup from O(n) to O(1), often the single biggest optimization.
5. Profile before optimizing: Theoretical complexity matters, but constants and cache behavior dominate at practical input sizes — always measure.
6. Watch for recursive space: Each recursive call adds a stack frame — O(n) recursion depth means O(n) space even if no explicit allocations occur.
7. Consider amortized costs: ArrayList add is O(1) amortized despite occasional O(n) resizes — don't over-optimize for rare expensive operations.
8. Be cautious with nested API calls: A loop calling list.contains() (O(n)) results in O(n²) — replace with a HashSet for O(n) total.
9. Document complexity: Annotate methods with their time and space complexity in comments — future maintainers will thank you.
10. Know your JDK complexities: Arrays.sort uses dual-pivot quicksort for primitives (O(n log n)) and TimSort for objects (O(n log n)) — leverage these.

Related Concepts

• High-Performance Streaming Operations: Understanding Big O is critical for evaluating streaming pipeline performance
• Asynchronous Programming: Complexity analysis applies to concurrent data structures and async operations
• REST HTTP Verbs and Status Codes: API response time is directly impacted by the algorithmic complexity of backend operations