Big-O Notation & Time Complexity

Big-O describes the growth rate of the work an algorithm does as the input size n increases. It ignores constants and machine speed so you can compare approaches before writing any code.

In system design, Big-O shows up everywhere: choosing a data structure for a cache, estimating the cost of a database scan versus an index lookup, or deciding whether a nested loop over every user will survive next year’s growth.

Diagram

Common complexity classes, from cheapest to most expensive as n grows.

Try it: how work grows

Key concepts

Time complexity: How the number of operations grows with input size.
Space complexity: How much extra memory the algorithm needs as input grows.
Worst vs average case: Quick sort averages O(n log n) but degrades to O(n²) on bad pivots. State which case you mean.
Amortised cost: An operation that is occasionally expensive but cheap on average, like appending to a dynamic array.
Dropping constants: O(2n) and O(n + 100) are both O(n). Constants still matter in practice, but not for growth.

Trade-offs

Benefits

Lets you compare designs before building them
Predicts behaviour at 10× or 100× the current data
Common vocabulary in code reviews and interviews

Costs

Hides constant factors and cache effects
Says nothing about I/O, network or lock contention
Small inputs can make a “worse” algorithm faster

Use it when

Choosing between data structures (list vs set vs map)
Reviewing code that loops over growing collections
Estimating whether a batch job will finish in its window

Common mistakes

Calling a database inside a loop — the hidden cost is network round trips, not CPU
Assuming O(1) means fast: a hash lookup with a slow hash function can still hurt
Ignoring memory: an O(n) cache of every request will eventually run out of RAM

Interview questions

Q1What is the complexity of looking up a key in a hash map, and when does it degrade?

Average O(1). It degrades towards O(n) when many keys collide into the same bucket, for example with a poor hash function or a deliberate collision attack.

Q2Why is binary search O(log n)?

Each step halves the remaining search space, so the number of steps is the number of times you can halve n before reaching one element: log₂ n.

Q3You find two nested loops over a list of users. Is that always a problem?

It is O(n²). With 100 users it is irrelevant; with 1 million it is 10¹² operations. Usually you can replace the inner loop with a hash set or map lookup to get O(n).

Diagram

Try it: how work grows

Key concepts

Trade-offs

Benefits

Costs

Use it when

Common mistakes

Interview questions

Related lessons

Latency Numbers & the Memory Hierarchy

Indexing & Query Performance

Caching Strategies