Programming · concepts · algorithms
What is Big O notation?
Big O notation is a way to describe how an algorithm's running time (or memory use) grows as its input gets larger. It answers one question: when the amount of data doubles, or grows a thousandfold, does your code stay fast, slow down a little, or grind to a halt? It deliberately ignores exact seconds and machine speed, and focuses on the shape of the growth - because that is what decides whether code that works on 100 items still works on 100 million.
Why not just measure the time?
Because seconds depend on the machine, the language, the compiler and what else is running. Run the same code on a laptop and a server and you get different numbers. Big O throws all of that away and measures something more durable: how the work scales with the input size, usually called n. Two algorithms can both take "a few milliseconds" on small input, yet one stays quick at scale while the other becomes unusable. Big O is how we tell them apart before we hit that wall.
The common complexities, best to worst
These are the growth rates you will meet most often, from the fastest-scaling to the most dangerous:
| Notation | Name | Rough idea |
|---|---|---|
| O(1) | Constant | Same work no matter the input size - e.g. reading array[5]. |
| O(log n) | Logarithmic | Halves the problem each step - e.g. binary search. |
| O(n) | Linear | Work grows in step with the input - e.g. scanning a list once. |
| O(n log n) | Linearithmic | The best you can do for general sorting - e.g. mergesort. |
| O(n²) | Quadratic | A loop inside a loop - fine for 100 items, painful for a million. |
| O(2ⁿ) | Exponential | Doubles with each added element - only usable for tiny inputs. |
| O(n!) | Factorial | Every ordering of the input - practical only for very small n. |
Why constants and small terms are dropped
Big O cares about growth, not exact counts, so it simplifies. If an algorithm does 2n + 3 steps, that is written O(n): the 2 and the 3 do not change the shape of the curve as n gets large. Likewise n² + n becomes O(n²), because the quadratic term dominates once n is big. This is why Big O is about the dominant term - the part that decides behaviour at scale - and not a precise stopwatch reading.
A concrete example
Say you want to check whether a list contains a duplicate. One approach compares every item with every other item - two nested loops, roughly n × n comparisons, so O(n²). Another approach adds each item to a hash set and checks membership as it goes - one pass, so O(n). On 1,000 items the quadratic version does about a million comparisons; on 100,000 items it does ten billion, while the linear version does 100,000. Same task, wildly different fate at scale. That gap is exactly what Big O is built to expose.
Worst, average and best case
Strictly, Big O describes an upper bound - usually the worst case, the most work the algorithm could do. You will also see two relatives: Big Omega (Ω) for the best case, a lower bound, and Big Theta (Θ) when the best and worst grow at the same rate, giving a tight bound. In everyday use people say "Big O" loosely to mean the worst-case growth, because that is what you plan around: you want to know how bad it can get, not how lucky you might occasionally be.
Space complexity, too
The same notation describes memory, not just time. An algorithm that copies the whole input into a new structure uses O(n) extra space; one that rearranges the input in place uses O(1) extra space. On large data, memory can be the real limit, so it is worth asking both "how does the time grow?" and "how does the memory grow?"
How to reason about your own code
- Count the loops over the input. One pass is usually O(n); a loop inside a loop over the same data is usually O(n²).
- Halving is a logarithm. If each step throws away half the remaining data (like binary search), that is O(log n).
- Lookups in a hash map/set are ~O(1). Replacing a nested scan with a hash lookup is the classic way to turn O(n²) into O(n).
- Drop the constants. Three separate single passes is still O(n), not O(3n) - the shape is what matters.
FAQ
Is a lower Big O always faster? At scale, yes - but not always for small inputs. Constants and overhead that Big O ignores can make an O(n²) method beat an O(n log n) one on a handful of items. Big O tells you who wins as the data grows, which is usually what matters.
What is the best possible complexity? O(1), constant time - the work does not grow with the input at all. Next best is O(log n). For problems that must look at every item at least once, O(n) is the floor.
Why is O(n log n) special for sorting? It is the proven lower bound for general comparison-based sorting, so mergesort, heapsort and good quicksort implementations all aim for it. You cannot generally sort arbitrary data faster by comparisons alone.
Do I need Big O for everyday coding? You do not need the formal maths, but the intuition is invaluable: recognising when a nested loop will explode on large input, or when a hash lookup saves you, prevents whole classes of performance bugs.