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.
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.