Time & Space Complexity (Big O) Explained with Examples

Every coding interview ends with "what's the time and space complexity?", and a surprising number of otherwise correct solutions lose points there. The usual failures are specific: calling a two-pointer loop O(n²) because it's nested, missing the O(n) hidden in a string slice, forgetting the recursion stack in space, or saying "O(n)" for a hash map solution without any idea what the worst case is.

This guide covers complexity analysis as a practical skill: how to read real code, loops, recursion and library calls included, and produce a correct bound with a one-sentence justification. It finishes with the most useful trick of all, going the other way: reading the input constraints to work out what complexity the intended solution must have.

What Big O Actually Means

Formally, f(n) = O(g(n)) if there are constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀. In words: beyond some input size, f grows no faster than g, up to a constant factor. Two consequences follow directly:

• Constants drop. 3n + 100 is O(n). So is n/1000.
• Lower-order terms drop. n² + 50n + 7 is O(n²), because for large n the n² term dominates.

O, Ω and Θ

In interviews, people say "Big O" and mean the tightest bound they can justify. Saying merge sort is O(n²) is technically true and practically useless; always give the tight bound.

Worst, average and best case are a different axis

A common confusion: "O is worst case, Ω is best case". Not so. Worst, average and best case describe which inputs you're analysing; O, Ω, Θ describe how tightly you bound the cost on those inputs. Quicksort's worst case is Θ(n²) and its average case is Θ(n log n). Hash map lookup is O(1) on average under reasonable hashing assumptions but O(n) in the worst case when everything collides. When you state a complexity, say which case you mean if they differ.

Common Complexity Classes, with Real Numbers

Abstract growth rates become much more intuitive when you plug in n. The table shows approximate operation counts for n = 10⁶ (and n = 20 for the exponential classes, since 10⁶ is hopeless there).

The jump between n log n and n² is where most interview problems live. At n = 10⁵, n log n is about 1.7 million operations and n² is 10 billion. That's the difference between instant and a timeout.

How to Analyse Loops: Rules and Worked Examples

The method is always the same: count how many times the innermost statement executes, as a function of n. The rules below are shortcuts for common shapes.

Rule 1: sequential blocks add, then the largest wins

for i in range(n):        # n
    work()
for i in range(n):        # n * n
    for j in range(n):
        work()
# total n + n^2 = O(n^2)

Rule 2: independent nested loops multiply

Two loops over n and m give O(n·m). Keep both variables when they're independent inputs. Saying O(n²) when the inputs are a string of length n and a pattern of length m loses information, and interviewers notice.

Rule 3: dependent loops need a sum

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)   // runs n-1, n-2, ..., 0 times
        check(i, j);
// total = n(n-1)/2 = O(n^2)

Halving the work doesn't change the class: visiting each pair once instead of twice is still quadratic.

Rule 4: multiplying or dividing the loop variable gives log n

i = 1
while i < n:
    i *= 2        # 1, 2, 4, ..., runs about log2(n) times

Base of the logarithm doesn't matter in Big O, because log₂n and log₁₀n differ only by a constant factor.

Rule 5: a loop to √n

i = 1
while i * i <= n:     # runs about sqrt(n) times
    i += 1

Rule 6: the harmonic pattern gives n log n

for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i)   // runs n/i times
        cnt[j]++;
// total = n/1 + n/2 + n/3 + ... + n/n = n * H(n) ≈ n ln n = O(n log n)

This looks quadratic at first glance. It's the pattern behind computing divisor counts for all numbers up to n, and a close relative of the Sieve of Eratosthenes, which only runs the inner loop for primes and is O(n log log n).

Rule 7: amortised pointer movement

left = 0
for right in range(n):
    while condition(left, right):
        left += 1
# left only increases and never exceeds n, so the inner loop runs at most
# n times IN TOTAL across all iterations: O(n), not O(n^2)

This is the argument behind every sliding window and monotonic stack solution. Nested loops are not automatically quadratic; what matters is the total number of inner iterations.

Quick quiz

The third row is the one people get wrong most: a geometric series of work that shrinks by half each time sums to a constant multiple of the first term.

How to Analyse Recursive Functions

For recursion, write a recurrence: the cost T(n) in terms of the cost of the recursive calls plus the non-recursive work. Then solve it with a recursion tree.

// T(n) = T(n-1) + O(1)  →  O(n)
int sum(int[] a, int i) {
    if (i == a.length) return 0;
    return a[i] + sum(a, i + 1);
}

// T(n) = 2T(n-1) + O(1)  →  O(2^n)
int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);   // (tighter bound is about 1.618^n)
}

// T(n) = T(n/2) + O(1)  →  O(log n)
int search(int[] a, int lo, int hi, int x) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == x) return mid;
    return a[mid] < x ? search(a, mid + 1, hi, x) : search(a, lo, mid - 1, x);
}

The recursion tree method: at each level, count the number of calls and the work per call, sum each level, then sum the levels. For merge sort, T(n) = 2T(n/2) + n: level 0 has 1 call doing n work, level 1 has 2 calls doing n/2 each (n total), level k has 2^k calls doing n/2^k each (n total). There are log₂n levels, so the total is n log n.

For branching recursion, the useful formula is (number of calls) × (work per call), and the number of calls is roughly (branching factor)^depth. Generating permutations has n choices, then n−1, and so on, giving n! leaves; copying each permutation costs n, so O(n·n!). More on reasoning about recursion trees is in recursion for beginners.

The Master Theorem for Divide and Conquer

For recurrences of the form T(n) = a·T(n/b) + Θ(n^d), with a ≥ 1 subproblems each of size n/b and n^d work to split and combine, compare d with log_ba:

This is the simplified form for polynomial f(n), which covers almost everything in interviews. Applying it:

When the Master Theorem doesn't apply

• Subtract-and-conquer: T(n) = T(n−1) + n is Θ(n²) (sum 1..n), and T(n) = 2T(n−1) + 1 is Θ(2ⁿ). Use the tree.
• Unequal splits: T(n) = T(n/3) + T(2n/3) + n. Every level of the tree does at most n work, and the longest path has log_3/2n levels, so it's Θ(n log n). (The Akra–Bazzi theorem handles this formally.)
• Quicksort's worst case: T(n) = T(n−1) + n = Θ(n²), which is exactly why pivot choice matters; see sorting algorithms compared.

Amortised Analysis: Why Append Is O(1)

Amortised cost is the total cost of a sequence of operations divided by the number of operations, in the worst case over sequences. It's not an average over random inputs; it's a guarantee about any sequence.

The dynamic array

An ArrayList, vector or Python list stores elements in a fixed-capacity block. When full, it allocates a bigger block and copies everything over. That single append costs O(n). So why is append called O(1)?

Suppose capacity doubles each time. Starting from capacity 1, n appends trigger copies of size 1, 2, 4, …, up to the largest power of two below n. That sum is less than 2n. Add the n ordinary writes and the total is under 3n, so each append is O(1) amortised.

#include <cstddef>
#include <algorithm>

class IntVec {
    int* data_ = nullptr;
    std::size_t size_ = 0, cap_ = 0;
public:
    void push_back(int x) {
        if (size_ == cap_) {
            std::size_t newCap = cap_ ? cap_ * 2 : 1;   // geometric growth
            int* bigger = new int[newCap];
            std::copy(data_, data_ + size_, bigger);     // O(size) copy, rarely
            delete[] data_;
            data_ = bigger;
            cap_ = newCap;
        }
        data_[size_++] = x;
    }
    ~IntVec() { delete[] data_; }
};

The growth factor doesn't have to be 2. Any constant factor above 1 gives amortised O(1). Real implementations differ: Java's ArrayList grows by about 1.5×, CPython's list over-allocates by roughly an eighth plus a small constant, and C++ std::vector growth is implementation-defined (commonly 2× in libstdc++ and 1.5× in MSVC). What does not work is growing by a fixed amount, say +100 each time: then n appends cause about n/100 copies of average size n/2, which is O(n²) total.

Other amortised examples you'll meet

• Monotonic stack: each element is pushed once and popped at most once, so n operations cost O(n) even though one push might pop many elements.
• Hash table resizing: rehashing on growth is O(n), amortised away by the same doubling argument.
• Union-find with path compression and union by rank: O(α(n)) amortised per operation, where α is the inverse Ackermann function, at most 4 for any practical n.
• Queue from two stacks: each element moves from the in-stack to the out-stack once, so dequeue is O(1) amortised.

Space Complexity: What to Count

Space complexity measures extra memory as a function of input size. Interviewers usually mean auxiliary space: memory beyond the input itself. Output arrays are sometimes excluded too (LeetCode's Product of Array Except Self explicitly excludes the output). If unsure, say what you're counting.

What counts:

• Data structures you allocate: a hash map of n entries is O(n); a fixed 26-letter count array is O(1).
• The recursion stack: depth × frame size. DFS on a balanced tree is O(log n), on a skewed tree O(n). Memoised recursion uses O(states) for the cache plus O(depth) for the stack.
• Hidden copies: slicing in Python, substring in Java (it copies since JDK 7u6), sorted() returning a new list.

A quick example of how the same problem trades time for space:

Laying out options like this, then asking which constraint matters more, is exactly the conversation interviewers want to have.

The Hidden Costs Inside Library Calls

Many wrong complexity answers come from treating a single line as O(1) when it isn't. These are the ones that matter most in interviews:

Note the "build heap is O(n)" row. Pushing n items one at a time is O(n log n), but heapify uses bottom-up sift-down, where most nodes are near the leaves and sift only a short distance. This occasionally comes up as a "gotcha" question about heaps.

Constraints to Complexity: Reading the Intended Solution

This is the most practical use of complexity analysis. The input limits in a problem statement tell you roughly what complexity is expected, which narrows the algorithm down before you've written anything. The table assumes the common rule of thumb of about 10⁸ simple operations per second for C++ and a 1–2 second limit; it's an approximation, and Python needs more headroom.

Two examples of using it. If n ≤ 10⁵ and your idea is O(n²), stop and look for sorting, hashing or a sliding window before coding. If n ≤ 20 and you're struggling to find a clever greedy, bitmask brute force is probably intended. Online assessments on HackerRank and similar platforms are where this pays off most, because a timeout gives no partial credit for a correct but slow solution; the online assessment tips go deeper on that.

Stating Complexity in an Interview

A strong complexity answer has three parts: the bound, which variables it's in terms of, and a one-sentence reason. For example:

"Time is O(n log n): sorting dominates, and the scan after it is linear. Space is O(n) for the sorted copy; if I can sort in place it's O(log n) for the sort's recursion stack."

Compare that with "O(n log n)" on its own. The first answer can be checked; the second invites follow-up questions you might fumble.

Mistakes that cost points

• Nested loop = n². Not when the inner loop's total work is bounded, as with two pointers or monotonic stacks.
• Ignoring hidden O(n) calls: list.pop(0), x in list, slicing, string concatenation, remove() on a list.
• Forgetting the recursion stack in space complexity.
• Using one variable for two inputs: say O(n + m) or O(n·m) when they're different sizes.
• Claiming hash maps are always O(1). Say "O(1) average" and know the worst case.
• Treating the output size as free. Generating all subsets is at least O(2ⁿ) because there are 2ⁿ of them.

Follow-up questions to rehearse

1. "Can you do better?" Compare your bound to the lower bound. Reading the input is Ω(n); comparison sorting is Ω(n log n). If you're already at the lower bound, say so.
2. "What's the worst case input?" For quicksort, already sorted data with a naive pivot; for hash maps, adversarial collisions.
3. "What if the data doesn't fit in memory?" Complexity shifts to I/O: external sort, streaming algorithms, approximate structures like a Bloom filter.
4. "Is this amortised or worst case per operation?" Matters for latency-sensitive systems, where a single O(n) resize can cause a spike.

Complexity analysis is also the first step of the problem-solving process: estimate, check constraints, then pick the pattern. The step-by-step guide to approaching a DSA problem shows how it fits into the full interview flow, and the same estimation instinct carries over into back-of-the-envelope estimation for system design.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.