Complexity analysis

You’ll recognise it when

• The problem gives limits like 1 ≤ n ≤ 2 · 10⁵. That number tells you how fast your solution must be.
• You have a correct brute force and want to know if it’s fast enough before you write it.
• The interviewer asks “what’s the time and space complexity?” They almost always do.
• Your code passes small tests but runs out of time on big ones.

Don’t confuse the worst case with the average case: a hash set lookup is O(1) on average but O(n) in the worst case.

The idea

At a party, you want to know whether any two guests share a birthday. One way: every guest talks to every other guest. With 10 guests that’s 45 conversations. With 300 guests it’s 44,850. Another way: put a calendar on the wall. Each guest checks their date as they arrive, then ticks it. That’s one glance per guest: 10 glances, or 300.

Both ways give the right answer. What differs is how the work grows when the party grows. Big-O describes exactly that. Count the basic steps as a function of the input size n, keep the fastest-growing term, and drop constant factors. 3n² + 5n + 100 steps is O(n²), because for large n the n² term swamps the rest.

Here is the “everyone talks to everyone” version in code:

def has_duplicate_slow(nums):
    for j in range(len(nums)):
        for i in range(j):             # every earlier value
            if nums[i] == nums[j]:
                return True
    return False

The inner loop runs 0, 1, 2, … n − 1 times, so there are n(n − 1)/2 comparisons: O(n²). The calendar version keeps a set of the values seen so far and does one lookup per value: O(n).

How it works

We’ll run the set version and, beside it, count what the pair version would do on the same input.

Scroll through the steps and the graphic follows along. You can also press play, step with the arrow keys, or edit the input: try one with no repeats to see the worst case.

Why it’s correct: when x is checked, seen holds exactly the values before it. So x in seen asks “has this value appeared earlier?”. The first yes is a duplicate, and if the loop ends, every value was new.

def has_duplicate(nums):
    """True if some value appears more than once in nums."""
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

#include <unordered_set>
#include <vector>
using namespace std;

// True if some value appears more than once in nums.
bool hasDuplicate(const vector<int>& nums) {
    unordered_set<int> seen;
    for (int x : nums) {
        if (seen.contains(x)) {
            return true;
        }
        seen.insert(x);
    }
    return false;
}

import java.util.HashSet;
import java.util.Set;

class Duplicates {
    // True if some value appears more than once in nums.
    static boolean hasDuplicate(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) {
            if (seen.contains(x)) {
                return true;
            }
            seen.add(x);
        }
        return false;
    }
}

Read the constraints first

A computer does very roughly 10⁸ simple steps per second in C++ or Java. Put the largest n into your complexity and compare. If n = 2 · 10⁵ and your idea is O(n²), that’s 4 · 10¹⁰ steps: several minutes, not one second. O(n log n) is about 2 · 10⁵ × 18 ≈ 4 · 10⁶: easy.

The same arithmetic, turned into a lookup table:

Python runs a simple loop step 10 or more times slower, so budget about 10⁷ steps per second. O(n²) is safe up to about 2,000. Built-ins like sorted, sum and set operations run in C, so they’re much faster than the same work written as a Python loop.

Count the loops

Loops one after another add: O(n) + O(n) is still O(n). Loops inside each other multiply: n outer steps times m inner steps is O(n · m).

When the inner bound depends on the outer loop, add up what the inner loop does on each pass:

for i in range(n):
    for j in range(i + 1, n):    # n-1, then n-2, ... then 0 steps
        ...

That’s (n − 1) + (n − 2) + … + 0 = n(n − 1)/2. Half of n², but still O(n²): the half is a constant factor.

Two more patterns come up all the time:

• An inner pointer that never goes back. In a sliding window, the inner while moves left forward. It looks nested, but left moves at most n times over the whole run, so the total is O(n). Count the total moves, not the worst case per outer step.
• An inner loop that doubles. Starting from j = 1, while j < n: j *= 2 runs about log₂ n times. Inside a loop over n, that’s O(n log n).

The usual way to beat an O(n²) pair loop is to remember something as you go: a set of values seen, a count per value, or a running sum.

Halving gives a logarithm

How many times can you halve n before you reach 1? About log₂ n times. That’s only 10 for a thousand, 20 for a million and 30 for a billion. Whenever each step throws away half of what’s left, expect a log: binary search, the height of a balanced tree or a heap, repeated doubling. The base doesn’t matter in Big-O, because log₂ n and log₁₀ n differ by a constant factor.

Recursion: add up the tree

For recursive code, draw the tree of calls and add up the work in it. Naive Fibonacci:

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

Each call makes two more, and the tree is up to n levels deep, so the number of calls roughly doubles with each level: O(2ⁿ). (The exact growth is about 1.6ⁿ.) fib(40) makes over 300 million calls. Yet only 41 different arguments exist. Store each answer the first time (memoisation) and it drops to O(n).

Merge sort splits the array in half, sorts each half, then merges in O(n). Add up the work one level of the tree at a time:

Each level does n work in total, and halving gives log₂ n levels: O(n log n).

Amortised cost: growing an array

A dynamic array (list, vector, ArrayList) keeps spare room at the end. When it’s full, it allocates a bigger block, say twice the size, and copies everything over. That one append costs O(n).

But copies are rare. Filling an array to n items copies 1 + 2 + 4 + … + n/2 items in total, which is less than n. So n appends cost less than 2n steps: O(1) amortised per append. Real libraries grow by between 1.125× and 2×, and any constant factor gives the same result. Amortised is a guarantee over the whole sequence, not a lucky average: no sequence of n appends can cost more.

Space: the call stack counts

Space complexity counts the extra memory your code uses beyond the input. Recursion uses memory too: every call waiting to return keeps a stack frame. A recursion d levels deep uses O(d) space even if it allocates nothing.

• Naive fib(n) takes O(2ⁿ) time but only O(n) space: only one path of the tree is on the stack at a time.
• Merge sort uses O(n) for the merge buffer plus O(log n) of stack.
• A recursive DFS on a path of 10⁵ nodes goes 10⁵ deep. Python stops at 1,000 by default, and deep enough recursion overflows the stack in C++ and Java too. Use an explicit stack.

The output usually doesn’t count as extra space. Say whether you’re counting it.

Why it’s O(n)

The loop runs at most n times. Each pass does one lookup and one insert, both O(1) on average, so the whole function is O(n) time. The set holds up to n values: O(n) extra space. (With a poor hash, or keys chosen to collide, a lookup can degrade to O(n). See hash maps.)

Three ways to solve the same problem, with the steps each takes at n = 2 · 10⁵:

The sort-based version is a fine answer too: it’s still fast, and it avoids hashing. Trading memory for time, as the set does, is the most common move in interviews.

Common mistakes

s = ""
for w in words: s += w        # ✗ can copy s every time: O(n²)
s = "".join(words)            # ✓ one pass: O(n)

common = [x for x in a if x in b]    # ✗ b is a list: O(len(a) · len(b))
b_set = set(b)
common = [x for x in a if x in b_set]   # ✓ O(len(a) + len(b))

while a: x, a = a[0], a[1:]      # ✗ copies the rest every time: O(n²)
for x in a: ...                  # ✓ O(n)

for x in stream: vals.append(x); top = sorted(vals)[-1]   # ✗ O(n² log n)
for x in stream: top = max(top, x)                        # ✓ O(n)

Variations

• Best, worst and average case. Big-O usually means the worst case. Hash lookups are the common exception, quoted as O(1) on average. Say which one you mean.
• Amortised against average. Amortised is a guarantee over any sequence of operations. Average is over random inputs, and one unlucky input can still be slow.
• More than one size. A graph is O(V + E), a grid O(rows · cols), two strings O(n · m). Keep the separate letters: collapsing them into one n hides real differences.
• Output-sensitive bounds. Listing every subset takes at least O(2ⁿ · n), because the output itself is that big. No clever trick beats the size of the answer.
• Big-Θ and Big-Ω. O is an upper bound, Ω a lower bound, and Θ both at once. In interviews “O(n)” usually means the tight bound. A classic lower bound: any sort that only compares items needs Ω(n log n) comparisons.