Big-O Notation, Explained Properly (In About 15 Minutes)

12 Jul 2026 4 min read

Big-O is a 15-minute concept that people stay vague about for years, and it costs them interviews — because “what’s the time complexity of your solution?” is the most reliably asked question in technical rounds. It’s also the question where a confident wrong answer does more damage than “I’m not sure.”

Here’s the whole thing.

What it actually measures

Big-O describes how the work grows as the input grows. Not how many seconds the code takes — that depends on your laptop, the language, and what else is running. It describes the shape of the growth curve.

That’s why two rules exist that look like cheating:

Drop the constants. O(2n) is O(n). Doing two passes over an array instead of one doesn’t change the shape of the curve — it’s still a straight line.
Drop the lower-order terms. O(n² + n) is O(n²). When n is large, the n² term is so dominant that the n stops mattering.

So Big-O is deliberately coarse. It answers “what happens when n gets big?”, which is exactly what an interviewer means when they ask whether your solution scales.

Reading complexity off the code

You can get most of the way with three patterns.

A loop over the input is O(n).

for i in 0..n:
    print(i)          // O(n)

Halving it doesn’t help: n/2 is still O(n), because that’s a constant factor.

A loop inside a loop is O(n²).

for i in 0..n:
    for j in 0..n:
        print(i, j)   // O(n²)

Careful, though — nested loops are only n² when the inner loop actually runs n times per outer iteration. Two loops one after another are O(n + m), not O(n × m). Sequential means add; nested means multiply.

A loop that cuts the problem in half is O(log n).

while n > 1:
    n = n / 2         // O(log n)

That’s binary search. It’s why searching a sorted array of a billion elements takes about 30 steps. And it’s why nobody writes the base of the log: changing base is a constant factor, so log₂ and log₁₀ are both just O(log n).

The complexities you’ll actually meet

Complexity	Name	Typical source
O(1)	Constant	Array index, hash lookup, push/pop
O(log n)	Logarithmic	Binary search, balanced tree operations
O(n)	Linear	One pass over the data
O(n log n)	Linearithmic	Efficient sorting (merge, heap, quick average)
O(n²)	Quadratic	Nested loops, bubble/insertion/selection sort
O(2ⁿ)	Exponential	Naive recursion over subsets

If your solution is O(n log n) there’s a good chance you sorted something. If it’s O(2ⁿ) and the constraints are large, the interviewer is waiting for you to notice.

The three things that separate a good answer from a vague one

1. Say which case you mean. Big-O without a case is ambiguous, and hash maps are the classic example: lookup is O(1) on average, but O(n) in the worst case when everything collides into one bucket. Quicksort is O(n log n) average and O(n²) worst. Saying “average case O(1), worst case O(n)” out loud signals you know why it’s not just O(1).

2. Don’t forget space. “Time O(n), space O(1)” is a complete answer; “O(n)” alone invites the follow-up. Recursion in particular has a space cost people miss — the call stack is real memory, so a recursion n levels deep is O(n) space even if it allocates nothing.

3. Know what “amortized” means, because you’ll say it by accident. Appending to a dynamic array is O(1) amortized: most appends are instant, but occasionally the array is full and everything gets copied to a bigger one, which is O(n). Spread across all the appends, the average cost per append is still constant. Amortized means “averaged over a sequence of operations”, not “usually”.

The mistake that costs the most

Reciting O(n log n) for your own code without being able to derive it.

Interviewers follow up. “Why log n?” has an answer — because each step halves the search space — and if you can say that sentence about your own solution, the complexity question is over and you’ve bought credibility for the rest of the round. If you can’t, they now know the recital was memorised, and they’ll dig.

So practise deriving it, not remembering it. Every time you finish a problem, before you look at anything else, say out loud what the complexity is and why.

Check whether it’s actually in your head

Reading this is the easy part. The time complexity quiz will tell you in about five minutes whether you can read complexity off unfamiliar code — which is the only version of this skill that matters in an interview.

Then take it into real problems: the DSA course is free, has written notes for every lesson, and calls out the complexity of every approach it covers — including the naive one you’re supposed to improve on.