Foundations

📘 Learn Foundations from zero

The problem: two algorithms both solve a task — which is "better"? Timing them on your laptop is misleading: faster hardware, a different language, or a lucky input all change the number. We need a measure that depends only on the algorithm and the size of the input, written n.

Analogy: imagine planning a road trip. You don't care that one route is "5 minutes faster on a Tuesday." You care how each route scales: does travel time grow with the number of cities linearly, or does it explode (visit-every-pair)? Asymptotic analysis is exactly this — how does the work grow as the input grows toward infinity? Constants (your car's speed) and small detours (lower-order terms) wash out; the growth rate is what survives.

Worked example: find the max in an array of n numbers. You look at each element once, keeping a running best. For n elements you do roughly n comparisons. If n doubles, the work doubles — that is linear time, O(n). Now count duplicate pairs by comparing every element to every other: for each of n elements you scan n others ≈ n² operations. Double n and the work quadruples — O(n²). We write 3n + 7 as just O(n): the 3 and the +7 are irrelevant once n is large, because the n term dominates.

Key insight: asymptotic notation describes how an algorithm's cost grows, not how long it takes. Big-O bounds it from above; Θ pins the exact growth rate when upper and lower bounds match. Either way you keep only the dominant term and drop constants, so you can compare algorithms independent of machine, language, or input luck.

✨ Added by the guide to build intuition — not from the source course.

🎯 Guided practice

Problem 1 (easy): What is the time complexity?

1. Code: for i in range(n): print(i) then separately for j in range(n): print(j).
2. Count each loop: the first runs n times, the second runs n times. Sequential blocks add: n + n = 2n.
3. Drop the constant factor 2 → O(n). Lesson: sequential code sums; constants vanish.
4. Contrast: if the second loop were nested inside the first, you'd multiply → n × n = O(n²). Nesting multiplies, sequencing adds.

Problem 2 (medium): Solve the recurrence for binary search and for merge sort.

1. Binary search recurrence: each call discards half the array and recurses on one half, doing O(1) work to pick the middle → T(n) = T(n/2) + O(1).
2. Recursion-tree view: each level does constant work, and you halve until size 1, so there are log₂ n levels → O(log n).
3. Merge sort: split in half, recurse on both halves, then merge in linear time → T(n) = 2T(n/2) + O(n).
4. Apply the Master Theorem with a=2, b=2, f(n)=n. Compute the watershed n^(log_b a) = n^(log₂ 2) = n¹ = n. Since f(n)=n = Θ(n^(log_b a)) — they match up to a log^k n factor with k=0 — this is Case 2, giving Θ(n^(log_b a) · log^(k+1) n) → Θ(n log n).
5. Pattern (the three cases): when you split into a subproblems of size n/b plus f(n) combine work, compare f(n) against the watershed n^(log_b a). If the watershed wins → Θ(watershed) (Case 1); a tie → ×log n (Case 2); if f(n) wins polynomially and satisfies the regularity condition → Θ(f(n)) (Case 3).

✨ Added by the guide — work these before the full problem set.