Big-O Complexity Classes, From O(1) to O(2ⁿ)

Big-O is not a grading scale and it is not a stopwatch. It answers one question: when the input gets bigger, what happens to the work? Everything else about it — the dropped constants, the ugly notation, the "asymptotic" — exists to make that question answerable without knowing your hardware.

The problem it solves

Two functions solve the same task. One takes 12 milliseconds on your laptop, the other 30. Which is better?

You cannot tell, because you measured one input on one machine. Run them on a thousand rows instead of ten and the ranking may flip. Big-O throws away everything that depends on the machine — the constant factors, the lower-order terms — and keeps the only thing that survives a change of scale: the shape of the growth.

That is why O(n²) beats O(n log n) on small inputs and loses catastrophically on large ones, and why the notation refuses to tell you where the crossover is. It is not measuring speed. It is measuring how badly speed degrades.

The six classes worth knowing

• O(1) — constant. One lookup, whatever the size: an array index, a hash get, arithmetic.
• O(log n) — logarithmic. Halve the problem every step: binary search, the height of a balanced tree.
• O(n) — linear. One pass over the input: a scan, a sum, a single loop.
• O(n log n) — linearithmic. A linear pass per halving level. This is what sorting costs.
• O(n²) — quadratic. Every pair: nested loops over the same collection.
• O(2ⁿ) — exponential. Two branches per element: every subset, unpruned recursion.

Their separation is not a matter of taste. Here is the work each class does, in steps, as the input grows:

import math

for n in (10, 100, 1000, 1_000_000):
    log_n = math.ceil(math.log2(n))
    print(n, log_n, n, n * log_n, n * n)

# 10       4       10       40           100
# 100      7       100      700          10000
# 1000     10      1000     10000        1000000
# 1000000  20      1000000  20000000     1000000000000

At a million inputs, O(log n) is doing 20 steps and O(n²) is doing a trillion. That is the whole argument for caring, and it is why the gap between classes matters far more than any constant inside one.

Watch it run

Each curve is one class, racing the same growing input. The interesting moment is not the finish — it is the crossover, where a curve that was flat stops being flat.

The shape to burn in is O(n log n) sitting just above O(n) and nowhere near O(n²). That is why "sort it first" is so often a good trade: sorting is nearly free compared to the quadratic scan it lets you avoid.

How to name your own code

Work outward from the loops. Three rules cover most interview answers:

1. Sequential blocks add, and addition keeps the biggest. A loop over n followed by another loop over n is O(n) + O(n) = O(2n) = O(n). A loop over n followed by a sort is O(n) + O(n log n) = O(n log n).
2. Nested loops multiply. A loop over n containing a loop over m is O(n·m). Over the same collection, that is O(n²).
3. Recursion is branches raised to depth, unless a table caches the repeats. Naive Fibonacci branches twice and recurses n deep, so O(2ⁿ); memoised, every distinct subproblem is computed once, so O(n).

Where it goes wrong

• Dropping the wrong term. O(n + m) over two different inputs is not O(n). Two separate sizes stay two separate letters, and interviewers notice when you collapse them.
• Confusing average with worst case. Hash lookup is O(1) on average and O(n) when every key lands in one bucket. Quick sort is O(n log n) on average and O(n²) on a bad pivot. Say which one you mean.
• Ignoring space. "Linear time" that builds a dictionary the size of the input is O(n) space too. A question about a stream, or about a very large file, is usually really a question about space.
• Counting the output. Producing every pair of n items cannot be faster than O(n²), because there are that many pairs. No cleverness beats the size of what you are asked to return.
• Hidden costs in built-ins. Slicing a Python list copies it. String concatenation in a loop rebuilds the string each time. list.insert(0, x) shifts everything. Each turns an intended O(n) into O(n²).

How to say it in an interview

Do not announce a class and stop. Justify it in terms of the input:

"The outer loop visits each of the n elements once. Inside, the lookup is against a set, so it is constant on average. That makes the whole thing O(n) time. I am storing one entry per element, so O(n) space as well. The worst case for the hash is every key colliding, which would make it O(n²), but with arbitrary keys that is not the case to design for."

Then offer the trade you did not take: "I could drop the set and keep it O(1) space, but that costs a nested scan — O(n²) time. Given the constraints, I would keep the memory." Naming the alternative you rejected is what separates a complexity answer from a recital.