What does Big-O notation describe? Find the complexity of a few typical code patterns, and explain how competitive programmers use the input limits (such as n ≤ 10^5) to choose an algorithm.
Show the explanation
Big-O gives an upper bound on how running time (or memory) grows as the input size n grows, ignoring constant factors and lower-order terms. 3n² + 10n + 7 is O(n²). Strictly, Big-O is an upper bound, Big-Ω a lower bound and Big-Θ a tight bound. In interviews "O" usually means the tight worst case.
Reading code
| Pattern | Complexity |
|---|---|
| a simple loop over n items | O(n) |
| two nested loops over n | O(n²) |
| halving the range each step (binary search) | O(log n) |
| a loop over n with a binary search inside | O(n log n) |
| sorting with a comparison sort | O(n log n) |
| recursion with 2 calls per level, depth n (naive Fibonacci) | O(2ⁿ) |
| trying every ordering (permutations) | O(n!) |
| hash map lookup | O(1) on average, O(n) in the worst case |
Sequential steps add (O(n) + O(n²) = O(n²)). Nested steps multiply.
Choosing an algorithm from the limits. A common rough rule of thumb is that a typical judge runs on the order of 10^8 simple operations per second. The real number depends heavily on the language and the operations, so treat this only as a guide. Within roughly a 1–2 second limit:
| n up to | Feasible complexity | Typical techniques |
|---|---|---|
| ~10–12 | O(n!) | permutations, brute force |
| ~20–25 | O(2ⁿ) | subsets, bitmask DP |
| ~500 | O(n³) | Floyd–Warshall, interval DP |
| ~5000 | O(n²) | simple DP, all pairs |
| ~10^5–10^6 | O(n log n) or O(n) | sorting, heaps, two pointers, prefix sums, BFS/DFS |
| ~10^9 or more | O(log n) or O(1) | binary search on the answer, maths, fast exponentiation |
Also consider
- Space complexity: a 10^4 × 10^4 table of ints needs about 400 MB, far over a typical 256 MB limit.
- Amortised cost:
vector::push_backorlist.appendis O(1) on average, even though an occasional resize is O(n). - Best, average and worst case: quicksort is O(n log n) on average and O(n²) in the worst case.
- Constants still matter in real systems. Big-O is about growth, not exact speed.
Original UniCircle question. Last reviewed 22 Oct 2026.