Big O and complexity analysis
Big O describes how an algorithm's running time (or memory use) grows as the input size n grows. It is not a measure in seconds — it is a measure of growth rate.
There are two separate measures:
- Time complexity — how many operations are executed
- Space complexity — how much memory is used beyond the input (the input itself usually doesn't count; this is called auxiliary space)
Big O always gives an upper bound and keeps only the dominant term as n approaches infinity. That's why 3n² + 100n + 5000 is simply O(n²): for large enough n, n² dwarfs everything else.
| Complexity | Name | Roughly, for n = 1,000,000 | Typical example |
|---|---|---|---|
| O(1) | constant | 1 operation | array index read, hash map lookup |
| O(log n) | logarithmic | ~20 operations | binary search, balanced-tree search |
| O(n) | linear | 1,000,000 | single pass over an array, finding the max |
| O(n log n) | linearithmic | ~20,000,000 | merge sort, quick sort, the language's sort() |
| O(n²) | quadratic | 10^12 — practically infeasible | two nested loops, comparing every pair |
| O(2^n) | exponential | incomputable | naive recursive fibonacci, all subsets |
How to derive complexity from a loop — simple rules:
- Sequential blocks add:
O(n) + O(n) = O(2n) = O(n) - Nested loops multiply: a loop running
ntimes inside a loop runningntimes =O(n²) - If the input halves at each step —
O(log n) - Constant factors and lower-order terms are dropped:
O(n/2)→O(n),O(n² + n)→O(n²)
Why constants are dropped: Big O measures the property that stays the same across machines and languages. Whether one operation takes 2 ns or 20 ns depends on the machine; that doubling the input quadruples the time is a property of the algorithm itself.
But constants do exist in practice: for n = 20 a simple O(n²) solution is often faster than a complicated O(n log n) one.
Best / average / worst case — how the same algorithm behaves on different inputs. Usually we talk about the worst case, because that's the guarantee.
Example — linear search in an unsorted array: best O(1) (the very first element), average O(n/2) = O(n), worst O(n) (the element is absent).
Amortized complexity — the average cost over a long sequence of operations. push on a dynamic array: usually O(1), but when capacity is full the array is doubled and copied — that single operation is O(n). Because growth happens ever more rarely, the total cost of n pushes is O(n), so push is amortized O(1).
Don't confuse amortized with average: average is about probability, amortized is an exact accounting over a sequence of operations.
Interview tip. Almost every coding question ends with: "What's the time and space complexity?" A strong answer has three parts: (1) state the figure, (2) justify why in one sentence, (3) mention whether something better exists. For example: "O(n) time because I make a single pass over the array; O(n) space because the hash map can hold up to n keys. There was an n² solution too — the hash map brought it down to n."
The most common mistakes: never mentioning space complexity at all; treating a sort() call as "free" and forgetting its O(n log n); adding nested loops instead of multiplying them; forgetting the call stack memory in recursion.