Foundations· 20 min
Big-O & Complexity Analysis
How algorithm cost grows with input — the language of DSA
n =16
O(1)1
O(log n)4
O(n)16
O(n log n)64
O(n²)256
O(2ⁿ)65.5K
O(2ⁿ) leaves the chart almost immediately on a linear scale — switch to log to compare all six classes.
What each class means
O(1)array[i], hash lookup
O(log n)binary search
O(n)linear scan
O(n log n)merge sort
O(n²)nested loops
O(2ⁿ)naive fibonacci
Rules of thumb for interviews
Reading code: a loop over n is O(n); a loop inside a loop is O(n²); halving the input each step is O(log n); sorting first costs O(n log n).
Judging limits: ~10⁸ simple operations per second. n ≤ 10⁵ needs O(n log n); n ≤ 10³ tolerates O(n²); n ≤ 20 allows O(2ⁿ).
Space counts too:an extra array is O(n) space; recursion depth uses the call stack — O(n) for a linear recursion, O(log n) for balanced divide & conquer.
Drop constants: O(2n) = O(n), O(n/2) = O(n), O(n² + n) = O(n²) — only the fastest-growing term survives.