Why Complexity Matters

What is this?

Complexity analysis is a way of describing how much work an algorithm does as a function of how much input it is given. It deliberately ignores the speed of your machine, the language you wrote it in, and how good the compiler is.

That sounds like throwing away useful information. It is the opposite: those details change constantly, and the shape of the growth does not.

Why does it matter?

Suppose two functions solve the same problem. On a thousand items, one takes 2 milliseconds and the other takes 1. The second looks twice as good. Now run both on a million items.

Input size	Linear approach	Quadratic approach
1,000	2 ms	1 ms
10,000	20 ms	100 ms
100,000	200 ms	10 seconds
1,000,000	2 seconds	~17 minutes

The same two functions, measured at four input sizes.

The slower-looking function wins at every size that matters. Its advantage at a thousand items was a constant factor; the other's disadvantage was structural. Constant factors stop mattering; growth rates never do.

The mental model

Concept

Count the work, not the clock

Ask how many times the innermost operation runs, expressed in terms of the input size n. That count is the algorithm's cost. Everything else — CPU speed, language, memory layout — scales that count by some constant, and constants are exactly what this analysis discards.

In practice this becomes a habit: read a loop and ask how many times it runs; read a nested loop and multiply; read a recursive call and ask how the problem shrinks.

A worked example

Scanning an unsorted array

InputAn array of n numbers, searching for a target

compare element 01 operation
compare element 12 operations
…the loop may run all the way
compare element n-1n operations total

Resultn comparisons in the worst case

The target might be first, in which case one comparison suffices. It might be absent, in which case every element is checked. Complexity analysis reports the worst case by default, because that is the guarantee you can rely on.

Reading code for cost

python

1def has_duplicate(nums):2    for i in range(len(nums)):          # runs n times3        for j in range(i + 1, len(nums)):  # runs up to n times4            if nums[i] == nums[j]:      # the innermost operation5                return True6    return False

Two nested loops over the same array

The inner comparison runs roughly n²/2 times. We drop the ½ — it is a constant — and call this quadratic.

Estimating whether something will finish

Interviewers give constraints for a reason. They are telling you which complexities are acceptable.

Constraint on n	What usually fits
n ≤ 20	Exponential — 2ⁿ or n! search
n ≤ 3,000	Quadratic — O(n²)
n ≤ 200,000	O(n log n) — sorting, heaps, binary search per element
n ≤ 10,000,000	Linear or better

A rough guide for a one-second budget.

Common mistakes

Timing code on one input and concluding one approach is faster in general.
Optimising a constant factor when the growth rate is the actual problem.
Forgetting that a library call inside a loop has its own cost — sorting inside a loop is not free.
Assuming fewer lines of code means less work.

Quick quiz

Try it on a real problem

1Running AltitudeEasy