If you test an algorithm with 10 elements and it takes 1 second, how long does it take with 100? 2 seconds? 10? 100?
The answer depends on the shape of the algorithm. That is exactly what BigO measures.
What BigO Notation is
BigO describes the asymptotic behavior of an algorithm: how the required time (or memory space) grows as the input size n grows, in the worst case.
It does not measure real seconds — real seconds depend on the hardware, the language, the compiler, and the phase of the moon. BigO measures the shape of the growth, independent of all those factors.
When we say an algorithm is O(n), we are saying that if you double the input, the time roughly doubles. If it is O(n²), doubling the input quadruples the time.
The complexity classes
| Notation | Name | Typical example |
|---|---|---|
| O(1) | Constant | Array access by index |
| O(log n) | Logarithmic | Binary search, operations on a balanced BST |
| O(n) | Linear | Traversing a list |
| O(n log n) | Linearithmic | MergeSort, HeapSort |
| O(n²) | Quadratic | Bubble sort, pairwise comparison |
| O(2ⁿ) | Exponential | Brute-force algorithms over subsets |
Which class you land in matters in production. The difference between O(n) and O(n²) is irrelevant with 10 elements. With a million elements, the difference is between a process that takes 1 second and one that takes 11 days.
Why "worst case"
BigO measures the worst case because that is what you need to guarantee. If your system has to respond in under 100ms under any condition, the average will not save you — the worst case will.
That said, there are variants:
- Big-O — worst case (the one everybody uses)
- Big-Ω (Omega) — best case
- Big-Θ (Theta) — tight bound: it holds as both ceiling and floor
In day-to-day engineering, when somebody says "it's O(n)", they usually mean the worst case.
How to read BigO in practice
O(1) — Constant. The input size does not matter, the time is the same. Accessing array[42] is O(1) because the memory address is computed directly.
O(log n) — Logarithmic. Each step discards half of the remaining candidates. Binary search over a sorted array: every comparison eliminates half of the search space. With 1 million elements, you need at most 20 comparisons.
O(n) — Linear. Time grows proportionally to the input. Finding an element in an unsorted list means checking every element in the worst case.
O(n²) — Quadratic. Typical of algorithms with two nested loops where the inner one walks the whole array for each element of the outer one. Fine for small inputs. Catastrophic at scale.
O(2ⁿ) — Exponential. Only useful for very small inputs. Computing every possible subset of a set is O(2ⁿ) — with 30 elements you are already talking about a billion operations.
The practical rule
When you analyze complexity, you drop the non-dominant terms and the constants. O(3n² + 5n + 2) simplifies to O(n²) because for large inputs the quadratic term completely dominates.
That simplification is intentional: BigO describes the shape of the growth, not the exact value. What matters is whether your algorithm grows linearly, quadratically, or some other way — the exact coefficient is an implementation detail.