Algorithms I: Analysis, Divide & Conquer, and Data Structures

Every algorithm faces two questions: is it correct, and how fast. Correctness is argued by induction (a loop/recursion invariant), by contradiction, or by an exchange argument (13b); speed is read off a recurrence, solved by the master theorem, a recursion tree, or substitution. On those rails sit the first design paradigm, divide & conquer — split, recurse, combine — and its two refinements: randomization, which buys a good expected runtime when no deterministic choice is safe, and the realization that comparison-based sorting cannot beat $\Theta(n\log n)$ (a counting lower bound), so linear-time sorts must avoid comparing. The closing third is the reusable speed primitives — data structures (heaps, balanced BSTs, hash tables) — whose entire job is to make a repeated operation cheap, almost always by guaranteeing $O(\log n)$ height or $O(1)$ expected lookup. A single meta-move recurs: write the work as a recurrence or a sum of indicator variables, then bound it. Prerequisites cashed in: logs and geometric/harmonic sums (track 1); induction and proof structure (track 2); indicator RVs, linearity of expectation, Bernoulli/geometric expectations (track 1); the quicksort/BST kinship to pivoting (this guide).

1. Asymptotics and proving runtimes

• The three bounds. $f = O(g)$ (upper, $\exists c, n_0:\ f(n) \le c\,g(n)\ \forall n\ge n_0$); $f = \Omega(g)$ (lower, $\ge$); $f = \Theta(g)$ (both — asymptotically tight). Little-$o$ is the strict version ($f/g \to 0$), a looser, absolute bound than $O$. Constants and lower-order terms wash out; what survives is growth rate.
• Proving an $O$ or $\Omega$ bound needs only one witness pair $(c, n_0)$ making the inequality hold for all $n \ge n_0$ — you don’t need it for all $c$. Proving $\Theta$ = prove $O$ and $\Omega$ separately.
• Disproving a claimed bound: by contradiction, manipulate the inequality until $n$ is pinned below/above a constant; then any $n$ past that constant breaks it.
• A bound to know cold: $\log(n!) = \Theta(n\log n)$. Upper: $n! \le n^n$ so $\log(n!) \le n\log n$. Lower: the top $n/2$ factors each exceed $n/2$, so $n! \ge (n/2)^{n/2}$ and $\log(n!) \ge \tfrac{n}{2}\log\tfrac{n}{2} = \Theta(n\log n)$. (This is the sorting lower bound of §5.)
• Correctness tools kept on hand: induction (state the invariant — what holds after iteration $i$ — then base case + inductive step), contradiction (assume the negation, derive impossibility), and the exchange argument for greedy (13b).

Core competency set

• State the $O/\Omega/\Theta/o$ definitions and what each asserts; prove a bound by exhibiting $(c, n_0)$.
• Prove $\log(n!) = \Theta(n\log n)$ both directions.

2. Recurrences — solving the cost of recursion

• The master theorem. For $T(n) = a\,T(n/b) + O(n^d)$ with constants $a\ge1,\ b>1,\ d\ge0$ ($a$ = number of recursive calls, $b$ = input-shrink factor, $d$ = exponent of the non-recursive “combine” work):

$T(n) = \begin{cases} O(n^d) & a < b^d \\ O(n^d \log n) & a = b^d \\ O(n^{\log_b a}) & a > b^d. \end{cases}$

• Why — the recursion tree (derive it). At level $j$ there are $a^j$ subproblems, each of size $n/b^j$, so the work at level $j$ is

$a^j \cdot c\Big(\tfrac{n}{b^j}\Big)^d = c\,n^d\Big(\tfrac{a}{b^d}\Big)^{j}.$

Summing over levels $j = 0, 1, \dots, \log_b n$ is a geometric series in ratio $r = a/b^d$:

• $r < 1$ ($a < b^d$): the series is dominated by its first term — the root does the most work → $O(n^d)$;
• $r = 1$ ($a = b^d$): every level does equal work $cn^d$, and there are $\log_b n$ levels → $O(n^d\log n)$;
• $r > 1$ ($a > b^d$): dominated by the last term — the leaves dominate, and there are $a^{\log_b n} = n^{\log_b a}$ of them → $O(n^{\log_b a})$.

So the whole theorem is one question: do subproblems proliferate ($a$) faster or slower than the per-call work shrinks ($b^d$)?

• Numeric anchor (one knob, three regimes): fix $b=2$ with a linear combine ($d=1$, so $b^d=2$) and vary only $a$. $a=1$: $T(n)=T(n/2)+O(n)$, $a<b^d$ → $O(n)$ (root-dominated). $a=2$: mergesort, $a=b^d$ → $O(n\log n)$ (every level equal work). $a=4$: $a>b^d$ → $O(n^{\log_2 4})=O(n^2)$ (leaf-dominated). The phase change sits exactly at $a=b^d=2$.
• General (CLRS) form for $T(n) = aT(n/b) + f(n)$: compare $f(n)$ to $n^{\log_b a}$; if $f$ is polynomially smaller → $\Theta(n^{\log_b a})$; equal (to within a log) → $\Theta(n^{\log_b a}\log n)$; polynomially larger and the regularity condition $a f(n/b) \le c f(n)$ for $c<1$ → $\Theta(f(n))$. (Case 3’s regularity condition is the one to check carefully.)
• Reshaping a recurrence to fit. For $T(n) = 2T(\sqrt n) + O(\log n)$: substitute $k = \log n$ (so $n = 2^k$), giving $T(2^k) = 2T(2^{k/2}) + O(k)$; define $S(k) = T(2^k)$ to get $S(k) = 2S(k/2) + O(k)$, solve by master ($a=b^d=2$ → $O(k\log k)$), then back-substitute $k=\log n$ → $O(\log n \log\log n)$.
• Substitution method (when the master theorem doesn’t apply — e.g. unequal children $T(n)=T(n/2)+T(n/4)+O(n)$): guess the answer, prove it by induction. Guess $T(n) \le cn\log n$; assume it for all $m<n$; substitute into the recurrence and choose $c$ (and $n_0$) so the inductive step closes. The signature trick for DSelect (§3): the two recursive fractions sum to less than 1, so the guess $T(n)\le cn$ survives — linear time.
• Recursion trees are also the most reliable hands-on tool. Picture (draw it): root = the size-$n$ problem; level $j$ has $a^j$ nodes of size $n/b^j$, each doing $c(n/b^j)^d$ work, so the per-level totals form the geometric series in $r=a/b^d$ — a top-heavy triangle if $r<1$ (root dominates), uniform bars if $r=1$, bottom-heavy if $r>1$ (leaves dominate). Draw the levels, size and count the work, sum.

Core competency set

• State the master theorem and derive its three cases from the recursion-tree geometric series ($r = a/b^d$).
• Solve a recurrence by substitution (guess + induct) and reshape one by variable substitution.

3. Divide and conquer

• The recipe: divide the input into smaller subproblems, conquer them recursively, combine. Always start with the brute force — it sets the runtime to beat — then ask: is any work duplicated or superfluous that the recursion can cut (Karatsuba’s 4→3 multiplications), or that an invariant lets you skip?
• Where the cleverness hides: in the combine step (mergesort’s merge), before the recursion (quicksort’s pivot/partition), or in the recursion structure itself. Heuristic: thinking about element values → consider sorting; thinking about indices/order → compare values at chosen indices; need a global answer (mergesort) vs. one element (search, select).
• Worked recurrences:
  • binary search $T(n) = T(n/2) + O(1) = O(\log n)$ (one recursive call, so $a<b^d$).
  • mergesort $T(n) = 2T(n/2) + O(n) = O(n\log n)$ ($a = b^d = 2$).
  • Karatsuba multiplies two $n$-digit numbers with 3 (not 4) subproducts: $T(n) = 3T(n/2) + O(n) = O(n^{\log_2 3}) \approx O(n^{1.585})$.
  • max-subarray: the max subarray lies in the left half, the right half, or crosses the midpoint; check the crossing one in $O(n)$ by extending outward from the middle, recurse on the two halves: $T(n) = 2T(n/2) + O(n) = O(n\log n)$.
• Selection (the $i$-th order statistic).
  • RSelect: pick a random pivot, partition, recurse on the side containing rank $i$ (no combine). A good (near-median) pivot gives $T(n) \le T(n/2) + O(n) = O(n)$; worst case $O(n^2)$; expected $O(n)$ because random pivots are usually good.
  • DSelect (deterministic linear): pick the pivot as the median of medians — split into groups of 5, take each group’s median, recurse to find their median. This guarantees the pivot beats/loses to at least 30% on each side (a split in the middle 40%), so

$T(n) \le T(n/5) + T(7n/10) + O(n).$

Since $\tfrac15 + \tfrac{7}{10} = \tfrac{9}{10} < 1$, substitution gives $T(n) = O(n)$ — the sub-call fractions summing below 1 is exactly what makes it linear.

• Design heuristics: a for-free primitive — if you’re already spending $\Omega(f)$, an extra step costing $O(f)$ (e.g. a sort) is free and may simplify everything; and converting a non-recursive method to recursive form can expose duplicate work to remove.

Core competency set

• State the D&C recipe and where the cleverness can hide; give the binary-search/mergesort/Karatsuba/max-subarray recurrences and answers.
• Explain RSelect (expected $O(n)$) and the DSelect median-of-medians split with the $\tfrac15+\tfrac{7}{10}<1$ argument.

4. Randomized algorithms

• The decomposition method (the core analysis skill): to bound an expected count, (1) name the count RV $Y$; (2) write it as a sum of indicator (0/1) variables $Y = \sum_l X_l$; (3) apply linearity of expectation $E[Y] = \sum_l E[X_l]$; (4) compute each $E[X_l] = P(X_l = 1)$ and sum. Linearity needs no independence — that’s what makes it powerful.
• Quicksort is $O(n\log n)$ expected (the canonical decomposition). Sorting elements $z_1 < \cdots < z_n$, let $X_{ij} = \mathbb 1[z_i, z_j$ ever compared$]$. They are compared iff one of $z_i, z_j$ is the first pivot chosen among the $j-i+1$ elements $z_i,\dots,z_j$ — if any element strictly between them is picked first, it splits them into different subarrays and they never meet. Of those $j-i+1$ equally-likely first picks, 2 cause a comparison, so

$P(X_{ij} = 1) = \frac{2}{\,j - i + 1\,}.$

Then by linearity,

$E[\#\text{comparisons}] = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{2}{j-i+1}.$

Each inner sum is at most $2H_n$ (the harmonic number $H_n = \sum_{k=1}^n \tfrac1k \approx \ln n$), and there are $n$ of them:

$E[\#\text{comparisons}] \le \sum_{i=1}^{n} 2H_n = 2nH_n = O(n\log n).$

(Picking the first element of a sorted array is the $O(n^2)$ worst case; the median pivot would match mergesort — random pivots get you there in expectation.)

• Las Vegas vs Monte Carlo. Las Vegas = always correct, runtime is random (quicksort, RSelect — randomness only affects speed). Monte Carlo = always fast, sometimes wrong (Karger, 13b — randomness affects correctness, repeat to drive failure probability down).
• Sums to keep handy: geometric $\sum_{k=0}^{K} r^k = \frac{1-r^{K+1}}{1-r}$, and for $r<1$ bounded by $\frac{1}{1-r}$; harmonic $H_n \approx \ln n$; $\sum_{i=1}^{n-1} f(i) \le \int_1^n f(x)\,dx$.

Core competency set

• State the 4-step decomposition method and run it for quicksort: $P(\text{compare } z_i,z_j) = \tfrac{2}{j-i+1} \Rightarrow O(n\log n)$.
• Contrast Las Vegas vs Monte Carlo with an example of each.

5. Sorting lower bound and linear-time sorts

• The comparison model as a decision tree. Any comparison-based sort is a binary tree: internal nodes are comparisons (“is $a_i < a_j$?”), the two branches are the boolean answers, and each leaf is one of the possible output orderings. Running the algorithm on a particular input traces one root-to-leaf path; the worst-case number of comparisons is the tree’s height.
• The $\Omega(n\log n)$ lower bound (count the leaves). A correct sort must be able to output any of the $n!$ permutations, so the tree has $\ge n!$ leaves. A binary tree with $L$ leaves has height $\ge \log_2 L$, so

$\text{height} \ge \log_2(n!) = \Theta(n\log n).$

Hence every comparison sort is $\Omega(n\log n)$ — deterministically in the worst case, and in expectation for randomized ones. Mergesort/heapsort meet it.

• Beating it requires not comparing — use the values themselves as addresses:
  • bucket sort: one FIFO bucket per possible value; drop each element into its bucket ($O(1)$), then concatenate buckets in order ($O(n)$). $O(n)$ total, but you must know the value range and it must be small.
  • radix sort: bucket-sort by one digit at a time, least-significant first, using FIFO buckets to preserve earlier order (stability). For $n$ integers up to $M$ in base $r$: $d = \log_r M + 1$ digits, $O(n+r)$ per pass, total $O(d(n+r))$. Choosing $r = n$ gives $O\!\big(n\,(\log_n M + 1)\big)$, which is $O(n)$ when $M \le n^c$ for constant $c$ — and degrades when $M \gg n$.

Core competency set

• Set up the decision-tree model and prove the $\Omega(n\log n)$ comparison lower bound via $n!$ leaves.
• Give bucket and radix sort and the condition ($M \le n^c$) under which radix is linear.

6. Data structures — the speed primitives

• The motivating tradeoff. A sorted array searches in $O(\log n)$ but inserts/deletes in $O(n)$ (shifting memory); a linked list inserts in $O(1)$ but searches in $O(n)$. Dynamic structures aim to get both — and the recurring lever is bounding the height of a tree to $O(\log n)$.

• Heap — a complete binary tree (every level full except the last, filled left-to-right) with the heap order (every node’s key $\le$ its descendants’). Supports fast insert and extract-min:

  • insert: place at the next open slot (keeps completeness), then bubble up — swap with the parent while smaller — at most $O(\text{height}) = O(\log n)$;
  • extract-min: the root is the min; remove it, move the last element to the root, then bubble down — swap with the smaller child while larger — $O(\log n)$.

  Array-backed (node $i$‘s children at $2i, 2i{+}1$); not a unique ordering of the elements. Numeric anchor: min-heap $[1,3,2]$, insert $0$ → place at slot 4 (under the $3$), bubble up: $0<3$ swap, then $0<1$ swap → $[0,1,2,3]$ (two swaps $=O(\log n)$). Extract-min: pop $0$, move last ($3$) to root, bubble down past the smaller child $1$ → back to $[1,3,2]$. Picture (draw it): a heap is a left-filled triangle, small-on-top; a balanced BST is the same triangle but sorted left-to-right (in-order traversal = sorted); a degenerate BST is a single diagonal chain of height $n-1$ — the picture of why balancing (red-black) matters.

• Binary search tree (BST) — invariant: every left descendant $<$ node $<$ every right descendant. In-order traversal (left, node, right) prints the keys sorted in $O(n)$. Search/insert/delete/min/max all walk one root-to-leaf path → $O(\text{height})$. Height is $\log n$ at best but $n-1$ for a degenerate chain — so balance is everything, and runtime is honestly stated as $O(\text{height})$.

• Red-black tree — a self-balancing BST. Invariants (4): (1) valid BST; (2) root is black; (3) a red node’s children are black; (4) every root-to-NIL path has the same number of black nodes (the “black-height”). These force the tree to stay within a factor 2 of balanced — red nodes mark where a path is getting long.

  • Height bound: $\text{height} \le 2\log_2(n+1) = O(\log n)$. Proof (induction on subtree size): claim a subtree rooted at $x$ with black-height $b(x)$ has $\ge 2^{b(x)} - 1$ internal nodes. Base: a single node. Step: with children $y, z$,

$k(x) = k(y) + k(z) + 1 \ge (2^{b(y)}-1) + (2^{b(z)}-1) + 1 \ge 2\big(2^{b(x)-1}-1\big) + 1 = 2^{b(x)} - 1,$

using $b(y), b(z) \ge b(x)-1$. So $n \ge 2^{b}-1$, giving black-height $b = O(\log n)$; since red nodes can at most double a path, the full height is $O(\log n)$. All operations are then $O(\log n)$.

• Hash table — $O(1)$ expected insert/delete/search when you don’t need ordering. Use chaining (a linked list per bucket); the goal is to spread $n$ keys evenly over $n$ buckets so chains stay length $O(1)$. The catch: for any fixed hash function an adversary can pick keys that all collide, so you must randomize the choice of function — but storing an arbitrary random function costs more than the table. Resolve with a universal family: a small family with

$P\big(h(u_i) = h(u_j)\big) \le \tfrac1n \quad \text{for } u_i \ne u_j.$

Then the expected bucket size for key $x_i$ is bounded:

$E[\text{size}] = 1 + \sum_{j\ne i} P\big(h(x_i)=h(x_j)\big) \le 1 + \frac{n-1}{n} \le 2,$

so search is $O(1)$ expected. Construction: pick a prime $p > |U|$ and set $h_{a,b}(x) = \big((ax + b) \bmod p\big) \bmod n$ for $a \in \{1,\dots,p-1\}, b\in\{0,\dots,p-1\}$ — a universal family of size $O(|U|^2)$ storable in $O(\log|U|)$ bits. (To check universality, find a key pair forced into the same bucket more than a $1/n$ fraction of the time — e.g. a plain “mod” family fails.)

Core competency set

• Give the sorted-array vs linked-list tradeoff and state heap insert/extract-min as $O(\log n) = O(\text{height})$.
• State the BST invariant and why runtime is $O(\text{height})$; list the 4 red-black invariants and prove the $O(\log n)$ height via $n \ge 2^{b}-1$.
• Explain why a fixed hash function is unsafe, define a universal family, derive $E[\text{bucket size}] \le 2$, and give the $((ax+b)\bmod p)\bmod n$ construction.

7. Memorize cold

• $O/\Omega/\Theta$ need one $(c, n_0)$ witness; $o$ is strict. $\log(n!) = \Theta(n\log n)$.
• Master theorem $T(n)=aT(n/b)+O(n^d)$: $a<b^d \to O(n^d)$; $a=b^d \to O(n^d\log n)$; $a>b^d \to O(n^{\log_b a})$. (Ratio $r=a/b^d$: root vs leaves.)
• mergesort $2T(n/2)+O(n)=O(n\log n)$; binary search $T(n/2)+O(1)=O(\log n)$; Karatsuba $3T(n/2)+O(n)=O(n^{\log_2 3})$; max-subarray $O(n\log n)$.
• RSelect expected $O(n)$; DSelect median-of-medians $T(n/5)+T(7n/10)+O(n)=O(n)$ (since $\tfrac15+\tfrac{7}{10}<1$).
• Decomposition: $E[Y]=\sum_l P(X_l{=}1)$. Quicksort: $P(\text{compare } z_i,z_j)=\tfrac{2}{j-i+1} \Rightarrow O(n\log n)$ expected.
• Las Vegas (always right, random time) vs Monte Carlo (always fast, sometimes wrong).
• Comparison sort lower bound: $n!$ leaves $\Rightarrow$ height $\ge \log(n!) = \Omega(n\log n)$. Radix $O(n)$ when $M \le n^c$.
• Heap / BST ops $= O(\text{height})$; balanced $\Rightarrow O(\log n)$. Red-black height $\le 2\log_2(n+1)$; proof $n \ge 2^{b(x)}-1$.
• Universal hashing: $P(\text{collision}) \le 1/n \Rightarrow E[\text{bucket}] \le 2$; $h_{a,b}(x) = ((ax+b)\bmod p)\bmod n$, $p>|U|$ prime.

Named moves (cross-track glossary): brute-force-first (sets the runtime to beat); recursion-tree (sum the geometric series in $a/b^d$ — root vs leaves); guess-and-induct (substitution method); reshape-the-recurrence (variable substitution $k=\log n$); decomposition-into-indicators ($E[Y]=\sum P(X_l)$, no independence needed — track 1); the-good-pivot (random or median-of-medians); fractions-sum-below-1 (DSelect linearity); count-the-leaves (decision-tree lower bound); don’t-compare (bucket/radix beat $n\log n$); $O(\text{height})$-then-balance (BST → red-black); randomize-the-hash (universal family defeats the adversary); for-free-primitive (a step inside your existing budget is free).