Two programs can produce exactly the same result and still behave completely differently once the amount of data grows. One finishes instantly with a million records; the other takes hours. Big O notation is the shared language programmers use to describe that difference, and it is far less intimidating than the symbols suggest.
What Big O actually measures
Big O describes how the work done by an algorithm grows as the size of the input grows. The input size is usually written as n: the number of items in a list, rows in a table, characters in a string, or nodes in a graph.
Notice what it does not measure. Big O is not a stopwatch. It does not tell you that a function takes 40 milliseconds, because that number depends on the machine, the language, the compiler and what else is running. Instead, it answers a more durable question: if the input becomes ten times larger, roughly how much more work will the algorithm do?
Because it focuses on growth, Big O deliberately ignores constant factors and lower-order terms. An algorithm that performs 3n + 50 steps is simply described as linear, or O(n). The constants matter in practice, but they do not change the shape of the curve.
The most common complexity classes
| Notation | Name | Typical example |
|---|---|---|
| O(1) | Constant | Reading an array element by index; looking up a key in a hash map. |
| O(log n) | Logarithmic | Binary search in a sorted array; descending a balanced tree. |
| O(n) | Linear | Scanning every item in a list once. |
| O(n log n) | Linearithmic | Efficient general-purpose sorting algorithms. |
| O(n²) | Quadratic | Comparing every item with every other item using nested loops. |
| O(2ⁿ) | Exponential | Brute-force exploration of every combination. |
The practical takeaway is the ordering. Constant and logarithmic algorithms stay comfortable no matter how much the data grows. Linear and linearithmic algorithms scale reasonably. Quadratic algorithms are fine for small inputs and painful for large ones. Exponential algorithms become unusable very quickly.
Reading complexity from your own code
You do not need advanced mathematics to estimate complexity. A few simple rules cover most everyday code:
- A single loop over the input that does constant work per item is O(n).
- A loop inside another loop, both running over the input, is O(n²). Three levels of nesting gives O(n³).
- Sequential blocks add up, and the largest term wins. A linear pass followed by another linear pass is still O(n).
- Halving the search space on each step produces a logarithmic term.
- Calls to library functions are not free. Sorting inside a loop, for example, often hides an O(n log n) operation.
That last point catches many developers. A loop that looks linear can quietly become quadratic if each iteration searches a list, concatenates a string or queries a database.
Best, average and worst case
The same algorithm can behave differently depending on the input. Searching a list for a value might find it on the first comparison or only on the last one. That is why three scenarios are usually discussed:
- Best case: the most favourable input arrangement.
- Average case: what typically happens with realistic data.
- Worst case: the arrangement that forces the maximum amount of work.
Big O is most often quoted for the worst case, because that is the guarantee you can rely on. When someone says a hash map lookup is O(1), they usually mean the average case; under heavy collisions the worst case degrades.
Time is not the only cost
Complexity also applies to memory. Space complexity describes how much additional storage an algorithm needs as the input grows. An in-place sort that rearranges an existing array uses constant extra space, while an approach that builds a full copy of the data uses linear extra space.
Many optimisations are trades between the two. Caching results speeds things up by spending memory. Recomputing values saves memory at the cost of time. Being explicit about which resource is scarce makes these decisions much easier to justify.
When Big O is the wrong tool
Asymptotic analysis describes behaviour as the input grows large. For small inputs, constants dominate, and a “worse” algorithm with a tiny constant factor can easily win. This is why some sorting libraries switch to a simple insertion sort for very short sequences.
It also ignores everything happening outside the algorithm itself: network latency, disk access, memory layout and cache behaviour. A linear scan over contiguous memory can outperform a theoretically better structure that scatters data across the heap.
The healthy approach is to use Big O to avoid clearly bad designs, then measure real performance with real data before optimising further. Profiling tells you where the time actually goes; complexity analysis tells you whether the problem will get worse as you grow.
Why it matters beyond interviews
Big O has a reputation as an interview topic, but its real value is everyday judgement. It helps you predict whether a feature that works fine with a hundred test records will survive a hundred thousand real ones. It explains why an index transforms a slow query, why nested loops over two large collections are a warning sign, and why choosing the right data structure often matters more than micro-optimising the code inside it.
If you want to build a solid foundation in algorithms, data structures and problem solving, the free courses in programming fundamentals, databases and software development available on Cursa are a practical place to continue.
