How to Analyze the Complexity of Any Code

In this lesson you learn the four rules that handle 95% of analyses. From here on, every complexity that appears in the course comes with its justification — and you'll be able to check each one.

Rule 1 — Blocks in sequence: add (and the largest wins)

If the code does one thing and then does another, the costs add up:

for x in nums:        # O(n)
    ...
for x in nums:        # O(n) again
    ...

Total: O(n + n) = O(2n) = O(n). Two separate loops are still linear! This is a classic mistake: seeing two for loops and shouting "O(n²)". It's only quadratic if one is inside the other.

If the blocks have different costs, the largest wins: sorting at O(n log n) and then scanning at O(n) gives O(n log n + n) = O(n log n).

Rule 2 — Nested loops: multiply

If for each turn of the outer loop the inner loop runs in full, the cost multiplies:

for i in range(n):        # runs n times...
    for j in range(n):    # ...and each time costs n
        ...               # total: n × n = O(n²)

The justification is literal: the body executes n × n times. And what if the inner loop is range(i + 1, n)? It runs n-1, then n-2, ... down to 1 time. The sum 1 + 2 + ... + n = n(n+1)/2 ≈ n²/2 — the ½ constant drops and it stays O(n²).

Watch out for the disguise: what multiplies is "how many times the inner one runs", not the number of for keywords in the text. An inner loop that always runs 10 times (fixed, not depending on n) gives n × 10 = O(n).

Rule 3 — Cutting in half: log

If at each step the problem divides (instead of shrinking by 1), the number of steps is logarithmic:

while n > 1:
    n = n // 2    # 1,000,000 → 500,000 → 250,000 → ... → 1

How many times can you divide 1,000,000 by 2 until you reach 1? About 20 (because 2²⁰ ≈ 1 million). That's log₂(n) — and we write O(log n). It's the signature of binary search, which you'll see in the Binary section.

And O(n log n)? It's O(log n) work repeated n times (or O(n) repeated log n times) — the cost of good sorting algorithms. The course's rule of thumb: "did I use sort? Then I'm already paying O(n log n)".

Rule 4 — The hidden cost of built-in operations

Every function call has a cost, even when it's a single line:

Operation	Cost	Why
`nums[i]`	O(1)	address computed directly
`x in hash_map` / `dict[x]`	O(1) on average	the superpower of the hash (next section!)
`x in list`	O(n)	has to look item by item
`list.sort()`	O(n log n)	rule 3 applied n times
`min(list)`, `max(list)`, `sum(list)`	O(n)	they scan everything
`list.insert(0, x)`	O(n)	shifts every element

The most common analysis mistake is forgetting these costs: an x in list inside a loop is an O(n) inside an O(n) — rule 2: O(n²) disguised as a single line.

Putting the rules to work

Analyze the code below before running it. What's the Big-O of each function? Use the rules and then check against the step count.

Carregando editor…

Answer key: misterio_a is O(n log n) — the sort dominates the sequence (rule 1 + rule 4). misterio_b is O(n log n) — a log n inside an n loop (rules 2 and 3).

The method in 3 questions

Faced with any code, ask:

How many times does each loop run? (n? half each time = log n? fixed = constant?)
Are they nested (multiply) or in sequence (add, the largest wins)?
Does any "one-line" operation have a hidden cost? (sort, list in, min/max...)

🧠 Practice quiz

0/5

1. A piece of code scans the array once and, for each element, does a binary search. What's the Big-O?

2. def f(nums): for x in nums: ... for y in nums: ... Two separate loops, one after the other. What's the Big-O?

3. Inside a loop over all n elements there is an `if x in list` (a plain list, not a set/dict). What's the total Big-O?

4. An algorithm sorts the array and then uses two pointers to scan it once. What's the Big-O?

5. A loop starts with j = n and does j = j // 2 until j reaches 1. About how many turns, for n = 1,000,000?

Summary

Sequence adds (the larger term wins); nesting multiplies.
Dividing in half = O(log n); sort = O(n log n).
"One-line" operations have a hidden cost — list in is O(n).
Analysis means answering: how many times each piece runs, and why.

In the next lesson: the other half of analysis — memory — and the quiz that wraps up the fundamentals.

All lessons in this section