Complexity by counting
Read complexity off the code by counting how many times the innermost line runs, then map the constraint to the complexity it permits.
On this page
Complexity has a reputation for being a topic you memorise. It is not: it is a count. Find the line that runs most often, work out how many times it runs as a function of the input size, and drop everything that is not the fastest-growing term. That is the whole method.
Count the innermost line
for i in range(n): # runs n times
for j in range(i, n): # runs n-i times for each i
total += a[i] * a[j] # the innermost line
The innermost line runs n + (n-1) + … + 1 = n(n+1)/2 times. Drop the constant
and the lower-order term: O(n²).
Two rules cover nearly everything:
- Nested loops multiply. A loop of n containing a loop of m is O(n·m).
- Sequential blocks add, then the larger one wins. O(n log n) followed by O(n) is O(n log n).
The one that trips people up is a loop whose bound shrinks. Halving is the
classic: while lo < hi: mid = (lo+hi)//2 runs about log₂n times, because you
can only halve n about log₂n times before reaching 1. At n = 10⁹ that is 30
iterations — which is why binary search feels like cheating.
The growth rates worth knowing cold
At n = 10⁵ (a very common constraint), assuming roughly 10⁸ simple operations per second:
| Complexity | Operations at n = 10⁵ | Feels like |
|---|---|---|
| O(log n) | 17 | instant |
| O(n) | 100,000 | instant |
| O(n log n) | 1.7 million | instant |
| O(n²) | 10¹⁰ | about two minutes — too slow |
| O(2ⁿ) | beyond counting | only viable for n ≤ ~25 |
The gap between n log n and n² at this size is a factor of six thousand. That is why "sort it first" is so often the answer: paying O(n log n) once to make the rest O(n) is nearly free.
Read the constraint backwards
The constraint is a hint about the intended solution, and it is the most reliable one you get:
| Constraint | Target | Usually means |
|---|---|---|
| n ≤ 20 | O(2ⁿ) or O(n!) | enumerate subsets or permutations |
| n ≤ 500 | O(n³) | interval DP, Floyd–Warshall |
| n ≤ 5,000 | O(n²) | pairwise DP, two nested loops |
| n ≤ 10⁵ | O(n log n) | sort, heap, binary search, or a single pass |
| n ≤ 10⁷ | O(n) | one pass, counting |
| n ≤ 10⁹ | O(log n) | binary search on the answer, or maths |
A value bound of 10⁹ with a small n is the strongest tell in the table: you are being asked to binary search over the answer, not over the array.
Space is counted the same way
Count what you allocate that grows with the input. A DP table of n by m is O(n·m); a set of every element is O(n); swapping in place is O(1). Recursion costs stack depth — a recursion that goes n deep is O(n) space even if it allocates nothing, which is exactly how a linked-list recursion blows up at n = 10⁵.
In an interview
State the complexity before you write the code, and state it as a count, not as a label: "this is O(n log n) — one sort, then a single pass." Naming the reason is what separates a rehearsed answer from an understood one.
Then use it. If the constraint says n = 10⁵ and your idea is O(n²), you have learned something before writing a line: keep looking. Candidates who skip this write the quadratic solution, discover it is too slow with four minutes left, and have no time to recover.
The mistake that loses points: giving a complexity for the algorithm while
ignoring a library call inside the loop. list.index(), in on a list, string
concatenation in a loop, and slicing are all O(n) — one of them inside an
O(n) loop silently makes your solution quadratic.
Check yourself
A function sorts an array, then runs a single pass with a nested loop that runs at most 3 times. What is the complexity?
O(n log n). The nested loop is bounded by a constant, so the pass is O(n), and the sort dominates.
The constraints say 1 ≤ n ≤ 30 and 1 ≤ value ≤ 10⁹. Where is the exponential allowed to be?
In n, not in the values. 2³⁰ is a billion — borderline — but anything proportional to the values is impossible. This shape usually means subsets with pruning, or meet-in-the-middle.
You recurse over a list of 10⁵ nodes, allocating nothing. What is the space complexity, and what will actually happen?
O(n) for the call stack — and in Python it will hit the recursion limit at around 1,000 frames. This is why linked-list problems at scale are written iteratively.