Time & Space Complexity (Big-O)

Prev Next

Big-O notation is the vocabulary that lets you and an interviewer agree on how "good" a solution is without running it. Get comfortable deriving it by reading code, not by pattern-matching to memorized labels — that's what lets you answer confidently when the interviewer tweaks your solution and asks "what's the complexity now?"

What Big-O Actually Measures

Big-O describes how the cost of an algorithm grows as the input size (conventionally called n) grows — it is a statement about growth rate, not a count of exact operations. An algorithm that does 5n + 100 operations and one that does 2n + 3 operations are both O(n): as n gets large, the constant factors and lower-order terms stop mattering compared to the shape of the curve. This is also why Big-O analysis conventionally drops constants and non-dominant terms — O(3n² + 50n + 7) is written simply as O(n²), because for large n the n² term dwarfs the rest.

There are two separate axes interviewers care about: time complexity (how the number of operations scales) and space complexity (how the extra memory you allocate scales — not counting the input itself, unless you're told otherwise). A solution can be fast but memory-hungry, or slow but memory-frugal; naming both explicitly is expected.

O(1) and O(log n)

O(1) — constant time: the cost doesn't depend on input size at all. Accessing an array by index is the canonical example, because the memory address is computed directly from the index — no scanning required.

public int firstElement(int[] arr) {
    return arr[0]; // direct memory access, regardless of arr.length
}

Time complexity: O(1) — a single array read, no matter how large the array is. Space complexity: O(1) — no extra memory allocated.

O(log n) — logarithmic time: the cost grows, but each step of work lets you discard a fraction of the remaining input (typically half). Binary search is the textbook case: every comparison cuts the search space in half, so for n items you need roughly log₂(n) comparisons.

public 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;
        else if (sorted[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Time complexity: O(log n) — the search space halves on every iteration, so the loop runs about log₂(n) times. Space complexity: O(1) — only a fixed handful of index variables, no matter how large the array is.

O(n) and O(n log n)

O(n) — linear time: the cost grows in direct proportion to the input — you touch every element roughly once.

public int max(int[] arr) {
    int best = arr[0];
    for (int value : arr) {
        if (value > best) best = value;
    }
    return best;
}

Time complexity: O(n) — one pass touching every element exactly once. Space complexity: O(1) — a single accumulator variable regardless of array size.

O(n log n) — linearithmic time: you do "linear work" a logarithmic number of times, or vice versa. This is the complexity class of every efficient general-purpose sort — merge sort splits the array in half recursively (log n levels) and merges each level in linear time.

public void sortIt(int[] arr) {
    Arrays.sort(arr); // backed by a dual-pivot quicksort / mergesort hybrid
}

Time complexity: O(n log n) — log n levels of splitting, each doing O(n) work to merge/partition. Space complexity: O(n) for the object-array overload used here (primitive-array Arrays.sort is typically in-place, O(log n) auxiliary space for its recursion).

O(n²) — Eyeballing Nested Loops

O(n²) — quadratic time: the fast rule of thumb interviewers expect you to apply instantly is: a loop nested inside another loop, both running roughly n times, is O(n²) — because for each of the n outer iterations, you do another n units of work, giving n × n = n².

public 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;
        }
    }
    return false;
}

Time complexity: O(n²) — the inner loop's total iteration count across all outer iterations sums to roughly n²/2, which is still O(n²) once constants are dropped. Space complexity: O(1) — no extra structures.

The eyeball trick: count the loops that scale with input size and multiply their bounds. Two independent nested loops over the same n → O(n²). Three levels deep → O(n³). A loop over n followed by a separate loop over n (not nested) → O(n) + O(n) = O(n), because they run one after another, not one inside the other. Watch out for loops hiding inside library calls too — list.contains() inside a loop over the same list is a hidden O(n²).

O(2^n) — Exponential Blowup

O(2^n) — exponential time: shows up when a recursive function branches into two (or more) calls at every level, without eliminating overlapping work. The classic offender is the naive recursive Fibonacci, which recomputes the same sub-values over and over.

public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // two recursive branches per call
}

Time complexity: O(2^n) — each call spawns two more calls, forming a binary call tree roughly n levels deep. Space complexity: O(n) — the call stack only ever holds one path down the tree at a time, even though the total number of calls is exponential. (This is exactly the kind of blowup that dynamic programming, covered later in this track, exists to fix.)

Big-O vs Big-Theta vs Big-Omega

In casual interview usage, "Big-O" is used loosely to mean "the complexity," but the three symbols technically mean different things:

Notation	Meaning	Example
O(f(n)) — Big-O	Upper bound. The algorithm never does worse than this (worst case).	Linear search is O(n): it never takes more than n comparisons.
Ω(f(n)) — Big-Omega	Lower bound. The algorithm never does better than this (best case).	Linear search is Ω(1): the target could be the first element.
Θ(f(n)) — Big-Theta	Tight bound. Upper and lower bound match — the algorithm always does about this much work.	Summing all elements of an array is Θ(n): always exactly n additions, no best/worst case gap.

In interviews you'll almost always be asked for the Big-O (worst-case) figure, since that's the safe bound to design around. Just don't be thrown off if an interviewer uses "Theta" or "Omega" precisely — knowing the distinction above is enough to not be caught out.

Next: With Big-O vocabulary in hand, we apply it to the simplest and most common data structure there is — see Arrays Basics.

Prev Next