Big-O Mastery

Complete Complexity Analysis — Phase 0, Weeks 1–2

Complexity analysis is the difference between knowing that a solution works and knowing why it’s acceptable. This document gives you the formal intuition, the mechanical derivation rules, and the amortized analysis tool — not as abstract theory, but as things you will actively use every time you write or evaluate code.

---

1. The Formal Definition (No Epsilon-Delta Required)

Big-O is a mathematical relationship between two functions. Informally: f(n) is O(g(n)) if, from some input size N₀ onward, f(n) never exceeds c·g(n) for some constant c.

The core intuition: We care about what happens as n grows large. Below N₀, any algorithm can beat any other algorithm because constants dominate. Above N₀, the growth rate determines the winner.

f(n) = O(g(n))  ←→  ∃ c > 0, N₀ > 0 such that f(n) ≤ c·g(n) for all n ≥ N₀

The three notations:

Notation	Meaning	Analogy
O(g(n))	Upper bound — algorithm does at most this much work	“It costs no more than…”
Ω(g(n))	Lower bound — algorithm does at least this much work	“It costs no less than…”
Θ(g(n))	Tight bound — algorithm does exactly this growth rate	“It costs exactly…”

Critical distinction: O is NOT “worst case.” O is an upper bound. You can say the best case of linear search is O(1) — it’s a valid upper bound on the best case. When people say “quicksort is O(n log n),” they mean average case. Merge sort’s worst case is Θ(n log n) — both upper and lower bound. Get this right.

Simplification rules (the ones you use every day):

• Drop constants: O(3n) = O(n), O(1000) = O(1)

• Drop lower-order terms: O(n² + n) = O(n²), O(n + log n) = O(n)

• Different variables stay separate: O(n·m) ≠ O(n²) unless you know n = m

---

2. Deriving Big-O: The Mechanical Rules

Rule 1: Single loops

A loop that runs n times → O(n). The body’s constant work doesn’t change this.

for i in range(n):       # n iterations
    arr[i] = arr[i] * 2  # O(1) per iteration

Total: O(n)

Rule 2: Nested loops

Multiply the number of iterations. But read the actual bounds — don’t assume.

for i in range(n):       # n iterations
    for j in range(n):   # n iterations per outer
        process(i, j)    # O(1)

Total: O(n²)

BUT:

for i in range(n):       # n iterations
    for j in range(m):   # m iterations per outer (m ≠ n)
        process(i, j)

Total: O(n·m), NOT O(n²)

AND:

for i in range(n):
    for j in range(i):   # i iterations, not n
        process(i, j)

Total: 0 + 1 + 2 + … + (n-1) = n(n-1)/2 = O(n²). But recognize the pattern.

Rule 3: Loops that halve — O(log n)

If the loop variable is halved (or some fraction) each iteration, it runs log₂(n) times.

i = n
while i > 1:
    process(i)
    i = i // 2   # halved each time

How many times can you halve n before reaching 1? log₂(n) times. → O(log n)

The intuition: Every time you cut the problem in half, you add one step. Starting from n=1024, it takes 10 halvings to reach 1. log₂(1024) = 10.

Rule 4: Recursive calls — write the recurrence

Don’t eyeball recursive code. Write T(n) = [cost per call] + [recursive calls on subproblems].

def merge_sort(arr):          # T(n)
    if len(arr) <= 1: return
    mid = len(arr) // 2
    merge_sort(arr[:mid])     # T(n/2)
    merge_sort(arr[mid:])     # T(n/2)
    merge(arr)                # O(n)

Recurrence: T(n) = 2T(n/2) + O(n) → see 02_recurrence_relations.md for solving this.

Rule 5: Sequential operations — add

for i in range(n):  # O(n)
    process(i)

for i in range(n):  # O(n)
    another(i)

Total: O(n) + O(n) = O(2n) = O(n). The loops run sequentially; you add their costs.

---

3. The 7 Complexity Classes

These cover 99% of what you’ll encounter. Know them cold.

Class	Name	Example	n=10	n=100	n=1000
O(1)	Constant	Array index access, hash map lookup	1	1	1
O(log n)	Logarithmic	Binary search, balanced BST ops	3	7	10
O(n)	Linear	Linear scan, sum of array	10	100	1000
O(n log n)	Linearithmic	Merge sort, heap sort	33	664	9966
O(n²)	Quadratic	Bubble sort, naive nested loops	100	10,000	1,000,000
O(2ⁿ)	Exponential	Recursive Fibonacci, subset enumeration	1024	2¹⁰⁰	2¹⁰⁰⁰
O(n!)	Factorial	Permutation generation, TSP brute force	3.6M	incomputable	incomputable

The practical cliff: For n = 10⁶ (one million), O(n log n) is ~2×10⁷ operations (fine). O(n²) is 10¹² operations (won’t finish in your lifetime without a supercomputer). The difference between “solves in 0.1s” and “never finishes” is often just one complexity class.

Codeforces rule of thumb: Modern computers do ~10⁸ simple operations per second. If your time limit is 1s and n = 10⁶, you need O(n log n) or better.

---

4. Space Complexity

Space complexity follows the same O/Θ/Ω notation. The critical thing most people miss: the call stack counts.

What to count:

• Variables you declare

• Data structures you allocate

• The recursive call stack (one frame per active call)

def factorial(n):   # T(n) = O(n), S(n) = O(n)
    if n == 0: return 1
    return n * factorial(n - 1)

This creates n stack frames simultaneously. Space: O(n), not O(1).

def factorial_iterative(n):  # S(n) = O(1)
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

One variable, no recursion stack. Space: O(1).

Space-time tradeoff: Memorization/caching trades space for time. Prefix sums use O(n) extra space to answer range queries in O(1) instead of O(n) each. Always state both complexities.

---

5. Amortized Analysis: The Dynamic Array Example

Amortized analysis asks: what is the average cost per operation over a sequence of n operations, even when some individual operations are expensive?

The problem: A dynamic array (ArrayList in Java, vector in C++) has capacity. When you push_back beyond capacity, it reallocates and copies everything — an O(n) operation. Does this make push_back O(n)?

No. Here’s why, worked out:

Suppose the array doubles in capacity each time it fills. Starting with capacity 1:

Capacity	Push cost
1→2	copy 1 element (cost: 1)
2→4	copy 2 elements (cost: 2)
4→8	copy 4 elements (cost: 4)
8→16	copy 8 elements (cost: 8)
…	…
n/2 → n	copy n/2 elements (cost: n/2)

Total copy cost for n pushes: 1 + 2 + 4 + 8 + … + n/2 = n - 1 (geometric series sum).

Total work for n push_back operations: n (for the pushes themselves) + (n-1) (for all copies) = 2n - 1.

Amortized cost per push_back: (2n-1)/n ≈ 2 = O(1).

This is why ArrayList/vector advertises O(1) amortized push_back. Any single push might cost O(n), but that cost is “paid for” by the n/2 cheap pushes that preceded it.

The mental model: Imagine each cheap push deposits a “credit.” When the expensive copy happens, it withdraws those credits. The credit never goes negative, so the average is constant.

---

6. What Most Engineers Get Wrong

Mistake 1: Confusing worst-case with Big-O. “Quicksort is O(n log n)” is sloppy language. Quicksort’s average-case is O(n log n). Its worst-case is O(n²) on adversarial input (already-sorted arrays with naive pivot). On competitive programming platforms, adversarial test cases are common. Always distinguish average-case from worst-case explicitly.

Mistake 2: Assuming built-in operations are always O(1). In C++, unordered_map (hash map) is O(1) average but O(n) worst-case due to hash collisions. There are documented competitive programming problems where adversaries construct inputs that trigger O(n) on every lookup, making your O(n) loop actually O(n²). This is not theoretical — it happens in Codeforces rounds.

Mistake 3: Dropping constants that matter in practice. O(n) with c=100 versus O(n log n) with c=1: for n < 10⁵, the “slower” O(n log n) may run faster. Big-O is asymptotic — it tells you what wins for large n, not for your specific n. Always sanity-check your constant factor when n is small.

Mistake 4: Treating nested loops as automatically O(n²). Two nested loops over different ranges is O(n·m). Two nested loops where the inner loop’s bound depends on the outer variable (e.g., for j in range(i)) requires summing the series. Always read the actual bounds.

---

7. Practice Problems

Problem 1. What is the time complexity of this code?

for i in range(n):
    for j in range(i, n):
        print(i, j)

Answer: The inner loop runs (n-i) times. Total iterations = Σ(n-i) for i=0..n-1 = n + (n-1) + … + 1 = n(n+1)/2 = O(n²).

---

Problem 2. What is the time complexity?

i = 1
while i < n:
    j = 1
    while j < n:
        print(i, j)
        j *= 2
    i *= 2

Answer: Outer loop: log n iterations. Inner loop: log n iterations. Total: O(log²n).

---

Problem 3. You have an algorithm: for each of n elements, run binary search on a sorted array of n elements. Total complexity? Answer: O(n log n). Binary search is O(log n), run n times.

---

Problem 4. What is the space complexity of this function?

def sum_array(arr, n):
    if n == 0: return 0
    return arr[n-1] + sum_array(arr, n-1)

Answer: O(n) space. Each recursive call adds one frame to the call stack, and there are n frames active simultaneously at the deepest point.

---

Problem 5. True or false: An O(n²) algorithm always runs slower than an O(n log n) algorithm. Answer: False. Big-O is asymptotic — for small n, constants dominate. An O(n²) algorithm with c=1 runs faster than an O(n log n) algorithm with c=1000 for n < 1000. Always consider the actual input size and constants.

---

Return to README.md · Next: 02_recurrence_relations.md