Big-O Notation — Measuring Time and Space Like an Engineer

Big-O Notation — Measuring Time and Space Like an Engineer

Big-O describes how the cost of an operation grows as input size (n) grows — not the exact runtime, which depends on hardware, language, and a hundred other things, but the shape of the growth curve. Learn to recognize the shape from code, not from memorizing a table.

O(1) — Constant Time

Cost doesn't depend on n at all.

int firstElement(int[] arr) {
    return arr[0]; // always one operation, regardless of array size
}

Array indexing, HashMap get/put (average case), pushing to a stack — all O(1).

O(log n) — Logarithmic Time

Cost grows, but the input shrinks by a constant factor each step, not a constant amount.

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

Each iteration halves the search space. 1,000,000 elements takes ~20 comparisons worst case, not 1,000,000. This is why sorted data plus binary search beats a linear scan by an enormous margin at scale — and why balanced trees and heaps (later in this path) are valuable specifically because they preserve O(log n) operations.

O(n) — Linear Time

boolean contains(int[] arr, int target) {
    for (int x : arr) if (x == target) return true; // one pass
    return false;
}

Cost scales directly with input size. A single loop over a collection is the signature.

O(n log n) — Linearithmic Time

The complexity of any comparison-based sort worth using in production — Arrays.sort(), Collections.sort(), merge sort, quicksort's average case. You'll see this constantly; it's the practical ceiling for "acceptably fast at real scale."

O(n²) — Quadratic Time

boolean hasDuplicate(int[] arr) {
    for (int i = 0; i < arr.length; i++)
        for (int j = i + 1; j < arr.length; j++)
            if (arr[i] == arr[j]) return true; // n * n comparisons
    return false;
}

Nested loops over the same collection. Fine at n=100 (10,000 operations, instant). Rough at n=100,000 (10 billion operations — this will time out or hang). The same duplicate-check done with a HashSet is O(n).

O(2^n) — Exponential Time

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // each call spawns two more
}

Naive recursive Fibonacci — each call branches into two more, unmemoized. Fine for n=10. Unusable for n=50. Module 5 covers memoization, which turns exactly this shape of problem into O(n).

The Table Worth Memorizing

Space complexity follows the same notation, describing memory instead of time — a recursive call stack n frames deep is O(n) space even if the time complexity is also O(n).