Common Complexity Classes

Almost every algorithm you encounter falls into one of a small set of complexity classes. Recognizing them is the fastest way to estimate performance.

The hierarchy

From fastest to slowest: $O(1) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$.

What each one means at scale

For $n = 10^6$, $O(n)$ is ~1 ms, $O(n \log n)$ is ~20 ms, $O(n^2)$ is unrunnable (~1000 seconds), and $O(2^n)$ is impossible for $n > 30$.

Examples per class

• $O(1)$: array indexing, hash map lookup, push/pop on a stack
• $O(\log n)$: binary search, balanced-tree operations, heap insert/extract
• $O(n)$: linear scan, single-pass aggregations, BFS/DFS over a sparse graph
• $O(n \log n)$: comparison-based sorting (merge sort, heap sort), divide-and-conquer that touches each element
• $O(n^2)$: nested loops over pairs, naive sorting, Floyd-Warshall on a small graph
• $O(2^n)$: enumerating subsets, naive recursive Fibonacci
• $O(n!)$: enumerating permutations, brute-force TSP

Practical takeaway

If you're handed a $10^5$-element input, you have time for $O(n \log n)$ comfortably and $O(n^2)$ only barely. At $10^6$, $O(n \log n)$ is your ceiling. At $10^8$, you need linear or sublinear. Knowing the input size and target class tells you which algorithm family to reach for before you write a single line.