Lesson

Complexity: Big O Made Simple

Why bother counting complexity

Picture this: you've written a solution, and it works on an example with three numbers. The interviewer asks, "What if there were a million numbers?" They don't care how many milliseconds the program takes. They want to know how the work grows as the input grows.

That's what Big O notation is for. It doesn't measure exact time. It describes the shape of growth: if the input gets 10 times bigger, how many times bigger does the work get?

An algorithm has two main measures:

Time: how many elementary steps it takes (comparisons, assignments, array accesses).
Space: how much extra memory it uses beyond the input (new arrays, dictionaries, recursion depth).

We drop constants and small stuff. 3n + 5 becomes O(n), and n² + n becomes O(n²). For large n, only the fastest-growing term matters.

The main complexities, with everyday examples

Complexity	Analogy	n = 10⁶ → roughly how many steps
O(1)	Opening a book at the bookmark. It doesn't matter how many pages it has	1
O(log n)	Looking up a word in a dictionary: open it in the middle, throw away half, repeat	~20
O(n)	Leafing through the whole book to find a typo	10⁶
O(n log n)	Putting a deck of cards in order the smart way (a good sort)	~2·10⁷
O(n²)	Every guest at a party shakes hands with every other guest	10¹² 😬
O(2ⁿ)	Trying every combination of pizza toppings: each one is either on or off	impossible

Remember one picture per row. In an interview, that's enough to estimate complexity on the spot.

How to count: a loop

One pass over an array means each element is visited once. There are as many steps as elements, so it's O(n).

152

i ↓ 163

234

425

Linear pass: pointer i moves left to right, each element is looked at once → O(n)

The classic example of such a pass is linear search:

def linear_search(arr, target):
    # look at each element in turn — O(n) time, O(1) space
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1  # not found

Two loops one after the other give O(n) + O(n) = O(2n), which is still O(n). Sequential steps add up.

How to count: nested loops

When a loop sits inside another loop, the steps multiply. For each i, the inner loop runs over up to n elements: n · n = O(n²). That's the "handshakes at a party" case. Example: counting pairs of equal elements.

def count_equal_pairs(arr):
    n = len(arr)
    count = 0
    for i in range(n):            # n times
        for j in range(i + 1, n): # up to n times for each i
            if arr[i] == arr[j]:
                count += 1
    return count  # O(n²) time, O(1) space

j starts at i + 1, so there are roughly n²/2 steps. But we drop the ½ constant, and it's still O(n²).

How to count: recursion

The formula is simple: number of calls × work per call.

Split the problem in half and go into only one half, like binary search. That's log n calls, so O(log n).
Split in half, solve both halves, and do O(n) work to merge, like merge sort. That's log n levels with O(n) work on each, for O(n log n) total.
Two recursive calls of almost the same size, like naive Fibonacci f(n-1) + f(n-2). The call tree doubles at every level, giving O(2ⁿ).

The space of recursion is measured by the depth of the call stack. For binary search it's O(log n); for Fibonacci it's O(n). People forget this a lot.

The input size hints at the solution

Rule of thumb: a computer does about 10⁸ simple operations per second. Look at the constraints in the problem, and you'll immediately see what complexity is expected of you:

Size n	Acceptable complexity
n ≤ 10–12	O(n!), trying all permutations
n ≤ 20–25	O(2ⁿ), trying all subsets
n ≤ 500	O(n³)
n ≤ 5,000	O(n²)
n ≤ 10⁵–10⁶	no worse than O(n log n)
n ≤ 10⁸	O(n)
even bigger	O(log n) or O(1)

See n ≤ 10⁵? A double loop almost certainly won't pass. Look for sorting, a hash map, or two pointers.

What it sounds like in an interview

State the complexity yourself, right away, without waiting to be asked:

"I go through the array once and keep the values in a hash set. Time is O(n), extra space is O(n). The naive version with two loops would be O(n²), which is too slow for n up to 10⁵."

That one sentence has time, space, a comparison with the naive solution, and a tie-in to the constraints. Interviewers really appreciate that.

Common mistakes

Forgetting about space. A new array, a dictionary, or the recursion stack all take up room.
Missing a hidden loop. x in list, arr.indexOf, slice, substring, and string concatenation in a loop are each O(n) on their own. Put one inside a loop, and you've got O(n²).
Multiplying sequential loops. When loops come one after another, their complexities add, they don't multiply.
Confusing "loop up to n" with "loop where i doubles." i *= 2 gives O(log n), not O(n).
Treating sorting as free. sort() costs O(n log n), and that has to show up in your final estimate.

You already know the most important part: look at code and say how it grows. From here on, say the complexity out loud for every problem, and after a couple dozen problems it'll be second nature.