Notes › DSA
Time & Space Complexity (Big-O)
Big-O describes how the running time (or memory) of an algorithm grows as the input size n grows. We ignore constants and smaller terms, because for big inputs only the dominant term matters.
3n² + 5n + 20→ O(n²)100n + 2→ O(n)n/2→ O(n) (constants drop)log₂ nandlog₁₀ n→ both O(log n) (they differ only by a constant)
Why it matters
A judge runs about 10⁸ simple operations per second. If n = 10⁵:
| Algorithm | Operations | Time |
|---|---|---|
| O(n log n) | ~1.7 × 10⁶ | instant |
| O(n²) | 10¹⁰ | ~100 seconds → TLE |
Common growth rates (fastest → slowest)
| Big-O | Name | Example |
|---|---|---|
| O(1) | constant | array access a[i], hash map lookup |
| O(log n) | logarithmic | binary search, balanced BST operations |
| O(√n) | square root | checking if n is prime |
| O(n) | linear | one loop over the array |
| O(n log n) | linearithmic | merge sort, heap sort, sorting in general |
| O(n²) | quadratic | two nested loops, bubble sort |
| O(n³) | cubic | three nested loops, Floyd–Warshall |
| O(2ⁿ) | exponential | all subsets, naive Fibonacci |
| O(n!) | factorial | all permutations |
Big-O, Big-Ω, Big-Θ
- O (upper bound): grows no faster than — what we usually quote, for the worst case.
- Ω (lower bound): grows at least as fast.
- Θ (tight bound): both. Linear search is O(n) in the worst case and Ω(1) in the best case (found at index 0).
Best, average, worst case are separate questions: quicksort is Θ(n log n) on average but O(n²) in the worst case.
Analysing loops
for (int i = 0; i < n; i++) sum += a[i]; // O(n)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) cnt++; // O(n²)
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) cnt++; // n(n-1)/2 → still O(n²)
for (int i = 1; i < n; i *= 2) cnt++; // O(log n): i = 1, 2, 4, 8 …
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++) cnt++; // n + n/2 + n/4 + … = 2n → O(n)!
for (int i = 1; i * i <= n; i++) cnt++; // O(√n)
Rules: consecutive blocks add (keep the biggest), nested blocks multiply, and loops that halve/double give a log.
The trap in the fifth example: the inner loop shrinks, so the total is a geometric series, not n log n.
Analysing recursion
Count calls × work per call, or write a recurrence.
| Code shape | Recurrence | Complexity |
|---|---|---|
f(n) = f(n-1) + O(1) (factorial) |
T(n) = T(n−1) + 1 | O(n) |
| binary search | T(n) = T(n/2) + 1 | O(log n) |
| merge sort | T(n) = 2T(n/2) + n | O(n log n) |
naive Fibonacci f(n-1) + f(n-2) |
T(n) = T(n−1) + T(n−2) + 1 | O(2ⁿ) (about 1.618ⁿ) |
| tree traversal | T(n) = 2T(n/2) + 1 | O(n) |
def fib(n): # O(2^n): the same values are recomputed again and again
return n if n < 2 else fib(n - 1) + fib(n - 2)
from functools import cache
@cache
def fib_fast(n): # O(n) with memoization — each value computed once
return n if n < 2 else fib_fast(n - 1) + fib_fast(n - 2)
Master theorem
For T(n) = a·T(n/b) + O(nᵈ):
- d > log_b a → O(nᵈ)
- d = log_b a → O(nᵈ log n)
- d < log_b a → O(n^(log_b a))
Merge sort: a = 2, b = 2, d = 1 → log₂2 = 1 = d → O(n log n). Binary search: a = 1, b = 2, d = 0 → log₂1 = 0 = d → O(log n).
Amortised complexity
vector.push_back / ArrayList.add is usually O(1) but sometimes O(n) when the array doubles. Over n pushes the total copying is n + n/2 + n/4 + … < 2n, so each push is O(1) amortised.
Space complexity
Count the extra memory you allocate (the input usually isn't counted):
| Code | Extra space |
|---|---|
| a few variables | O(1) |
| a new array / hash map of n items | O(n) |
| a 2-D DP table n × m | O(n·m) |
| recursion of depth d | O(d) — the call stack counts |
Recursive DFS on a skewed tree uses O(n) stack; on a balanced tree O(log n).
Reading the constraints
| n up to | Aim for |
|---|---|
| 10–12 | O(n!) |
| 20–25 | O(2ⁿ) |
| 500 | O(n³) |
| 5,000 | O(n²) |
| 10⁵ – 10⁶ | O(n log n) or O(n) |
| 10⁹ and more | O(log n) or O(1) |
Practice: what's the complexity?
- Two separate loops of n → O(n).
- A loop of n with a binary search inside → O(n log n).
- Sort, then one loop → O(n log n).
for i in range(n): for j in range(i, i+5)→ O(n) (the inner loop is constant).- Checking every pair with a hash set inside → O(n²) time, O(n) space.
Interview one-liners
- Big-O drops constants and lower terms; it describes growth, not exact time.
- Nested loops multiply, sequential loops add, halving gives log n.
- Recursion uses stack space equal to its depth.
- Hash maps are O(1) average, O(n) worst case.
- Full reference table: Big-O Complexity. Next: Arrays & Two Pointers.