Complexity Explorer
Big-O tells you how work grows with input size. Drag n and watch the gap between classes explode — then read the constraint table to translate a problem's limits into an acceptable complexity.
Typical examples
| Complexity | Typical example | Ops at n = 16 | Learn |
|---|---|---|---|
| O(1) | Hash lookup, array index, stack push/pop | 1 | → |
| O(log n) | Binary search, balanced BST operations, heap push/pop | 4 | → |
| O(n) | Linear search, one pass over an array, BFS/DFS on a tree | 16 | → |
| O(n log n) | Merge sort, heap sort, sorting then sweeping | 64 | → |
| O(n²) | Nested loops, bubble/insertion sort, naive LIS | 256 | → |
| O(n³) | Floyd-Warshall, matrix chain DP, triple loops | 4,096 | → |
| O(2ⁿ) | Subset recursion, bitmask enumeration, naive Fibonacci | 6.55 × 10^4 | → |
| O(n!) | Permutations, brute-force TSP | 2.09 × 10^13 | → |
Reading constraints
Roughly 10⁸ simple operations per second is a common budget. These are rules of thumb, not guarantees — constant factors, memory access patterns and the judge's time limit all matter.
| Constraint | Aim for | Why |
|---|---|---|
| n ≤ 10 | O(n!) or O(2ⁿ · n) | Even factorial-time brute force finishes: 10! ≈ 3.6 million. |
| n ≤ 20 | O(2ⁿ · n) | Bitmask DP / subset enumeration: 2²⁰ ≈ 1 million states. |
| n ≤ 500 | O(n³) | 1.25 × 10⁸ simple operations — Floyd-Warshall, interval DP. |
| n ≤ 5·10³ | O(n²) | 2.5 × 10⁷ — nested loops, O(n²) DP (LCS, LIS naive). |
| n ≤ 10⁵ | O(n log n) or O(n) | Sorting, heaps, binary search, segment trees, sweeps. |
| n ≤ 10⁶ | O(n) — maybe O(n log n) | Linear scans, prefix sums, hashing, sieve, KMP. |
| n ≤ 10⁹ (or larger) | O(log n) or O(√n) | Binary search on the answer, fast exponentiation, math. |
How to use this
Read the largest constraint first. If n ≤ 20 an exponential approach (bitmask DP, backtracking) is intended; if n ≤ 10⁵ the problem is telling you an O(n²) solution will time out and you should look for sorting, hashing, binary search, heaps, or a linear sweep.Caveats
Space limits, recursion depth, cache behavior and language speed shift these boundaries. A tight O(n²) in C++ at n = 10⁴ is fine; the same in Python may not be. Amortized and expected bounds (hash tables, quicksort) are usually what matters in practice.