Exercises — Divide and conquer — template, correctness, recurrence

• $a=4$ (four recursive calls), $b=2$ (each child is half-size), $f(n)=n$.
• $c_{\text{crit}}={\log }_{2}4=2$.
• Compare $f(n)=n=n^1$ with $n^2$: since $1<2$, $f$ is polynomially smaller ⟹ Case 1.
• Answer: $T(n)=\Theta (n^2)$.

• "Cut the array in half" is Divide — it produces the two subproblems.
• merge is Combine — it glues two sorted halves into one sorted whole.
• The two recursive mergesort calls are the Conquer phase.

• Binary Search → $T(n/2)+\Theta (1)$ (one recursive call, constant compare).
• Mergesort → $2T(n/2)+\Theta (n)$ (two halves, linear merge).
• Karatsuba → $3T(n/2)+\Theta (n)$ (three half-size multiplies, linear add/shift).

• $a=9,b=3,f(n)=n$.
• $c_{\text{crit}}={\log }_{3}9=2$.
• $f(n)=n=n^1$ vs $n^2$: $1<2$ ⟹ Case 1.
• $T(n)=\Theta (n^2)$.

• $a=2,b=2,f(n)=n^2$; $c_{\text{crit}}={\log }_{2}2=1$.
• $f(n)=n^2$ vs $n^1$: $2>1$, so $f$ is polynomially larger ⟹ candidate Case 3.
• Regularity check: $af(n/b)=2(n/2{)}^2=2\cdot n^2/4=n^2/2=\frac{1}{2}f(n)$. With $k=\frac{1}{2}<1$ ✓.
• Case 3 confirmed: $T(n)=\Theta (f(n))=\Theta (n^2)$.

• $a=7,b=2,f(n)=n^2$; $c_{\text{crit}}={\log }_{2}7\approx 2.807$.
• $f(n)=n^2$ vs $n^{2.807}$: $2<2.807$ ⟹ $f$ smaller ⟹ Case 1.
• $T(n)=\Theta (n^{{\log }_{2}7})\approx \Theta (n^{2.807})$.
• Meaning: Strassen beats naïve $\Theta (n^3)$ matrix multiply because ${\log }_{2}7<3$.

• $a=2,b=2$, so $c_{\text{crit}}=1$ and $n^{c_{\text{crit}}}=n$. Here $f(n)=n\log n$.
• Is $f$ polynomially bigger than $n$? We would need $n\log n=\Omega (n^{1+\epsilon })$ for some $\epsilon >0$. But $\log n$ grows slower than $n^{\epsilon }$ for every $\epsilon >0$, so no such $\epsilon$ exists. The gap is only logarithmic: $f$ is neither polynomially smaller (Case 1) nor $\Theta (n)$ (plain Case 2) nor polynomially larger (Case 3). So the plain three-case statement gives no answer. (It is covered by the generalized Case 2 with $k=1$ from our definition above — and we confirm that answer by hand below.)
• Recursion tree. Level $i$ has $2^i$ nodes each of size $n/2^i$, doing $f(n/2^i)=\frac{n}{2^i}\log \frac{n}{2^i}$ work. Level total: $2^i\cdot \frac{n}{2^i}\log \frac{n}{2^i}=n\log \frac{n}{2^i}=n(\log n-i).$
• Sum over $i=0$ to ${\log }_{2}n-1$: ${\sum }_{i=0}^{{\log }_{2}n-1}n(\log n-i)=n{\sum }_{j=1}^{{\log }_{2}n}j=n\cdot \frac{(\log n)(\log n+1)}{2}=\Theta (n{\log }^{2}n).$
• Answer: $T(n)=\Theta (n{\log }^{2}n)$ — matching generalized Case 2 ($c_{\text{crit}}=1,k=1\Rightarrow n^1{\log }^{2}n$).

• The two children shrink by different factors, so plain MT (which needs one clean $b$) does not apply.
• A monotonicity note first. All the bounds below use that $T$ is nondecreasing in $n$ (bigger input ⟹ at least as much work). This holds because the recurrence's non-recursive term $n$ is nondecreasing and the recursive calls are on nonnegative sizes, so a standard induction shows $T(m)\le T(n)$ whenever $m\le n$. We assume this throughout.
• Upper bound. Since $T$ is nondecreasing, $T(n/4)\le T(n/2)$, so replacing the smaller child by the bigger one can only increase the total: $T(n)\le 2T(n/2)+n$, which is Case 2 ⟹ $O(n\log n)$.
• Lower bound. The root alone does $n$ work, so $T(n)=\Omega (n)$.
• Why the total input size at each level multiplies by $\frac{3}{4}$. Each node of size $s$ spawns two children of sizes $s/2$ and $s/4$, whose sizes add to $s/2+s/4=\frac{3}{4}s$. So if the sizes of all nodes at level $i$ add up to $S_i$, then summing this over every node gives $S_{i+1}=\frac{3}{4}{S}_i$. Starting from $S_0=n$ (the root), we get $S_i=n(\frac{3}{4}{)}^i$.
• Sharper tree sum. The non-recursive work at a node equals its size (the $+n$ term is linear), so level-$i$ work $=S_i=n(\frac{3}{4}{)}^i$, a geometric series: ${\sum }_{i\ge 0}n{\left(\frac{3}{4}\right)}^i=n\cdot \frac{1}{1-\frac{3}{4}}=4n=\Theta (n).$
• Since the series converges, the root dominates: $T(n)=\Theta (n)$ (which also tightens the loose $O(n\log n)$ upper bound above).

• Guess: $T(n)\le cn{\log }_{2}n$. We find $c$ by induction on powers of 2.
• Base $n=2$: $T(2)=2T(1)+2=2\cdot 1+2=4$. We need $c\cdot 2\cdot {\log }_{2}2=2c\ge 4$, i.e. $c\ge 2$.
• Step: assume $T(n/2)\le c\frac{n}{2}{\log }_2\frac{n}{2}$. Then $T(n)=2T(n/2)+n\le 2\cdot c\frac{n}{2}{\log }_2\frac{n}{2}+n=cn({\log }_{2}n-1)+n=cn{\log }_{2}n-cn+n.$
• This is $\le cn{\log }_{2}n$ iff $-cn+n\le 0$, i.e. $c\ge 1$. Combined with the base's $c\ge 2$, choose $c=2$.
• Therefore $T(n)\le 2n{\log }_{2}n=O(n\log n)$. ∎

• Recall from the header that the non-recursive term is $f(n)=D(n)+C(n)$: the divide cost plus the combine cost.
• Divide: split the array into left and right halves ($a=2$, $b=2$; the split is just index arithmetic, so $D(n)=\Theta (1)$).
• Conquer: recursively find the max of each half.
• Combine: return the larger of the two returned maxima — one comparison, so $C(n)=\Theta (1)$.
• Hence $f(n)=D(n)+C(n)=\Theta (1)+\Theta (1)=\Theta (1)$.
• Base: a single element is its own max.
• Recurrence: $T(n)=2T(n/2)+\Theta (1)$. Then $a=2,b=2,c_{\text{crit}}=1$, $f(n)=\Theta (1)=\Theta (n^0)$; since $0<1$ ⟹ Case 1 ⟹ $T(n)=\Theta (n^1)=\Theta (n)$.
• Comparison: same $\Theta (n)$ as a linear scan — divide and conquer buys nothing here because there is no cheap combine advantage; every element must still be looked at once. (Useful lesson: D&C only wins when the combine is cheaper than re-solving.)

• The proposal is not valid: to split each sorted array "in half" and merge crosswise, the halves you pick are not guaranteed to interleave cleanly — an element in the left half of array A can be larger than one in the right half of array B, so the four merges overlap. The subproblems are not independent, breaking the paradigm's precondition.
• The correct merge is a single linear pass with two pointers: $\Theta (n)$, no recursion inside the merge itself.
• Inside Mergesort the full recurrence is $T(n)=2T(n/2)+\Theta (n)$ where the $\Theta (n)$ is this two-pointer merge. Case 2 ⟹ $\Theta (n\log n)$.

• New: $a=5,b=3$, $c_{\text{crit}}={\log }_{3}5\approx 1.4650$.
• $f(n)=n=n^1$; $1<1.465$ ⟹ Case 1 ⟹ $T(n)=\Theta (n^{{\log }_{3}5})\approx \Theta (n^{1.465})$.
• Karatsuba is $\Theta (n^{{\log }_{2}3})\approx \Theta (n^{1.585})$.
• Since $1.465<1.585$, the new scheme is asymptotically faster. (This is the real Toom–3 algorithm.)

• $c_{\text{crit}}={\log }_{2}a$; compare $f(n)=n=n^1$ against $n^{{\log }_{2}a}$.
• $a<2$: ${\log }_{2}a<1$, so $f$ is bigger ⟹ Case 3 (regularity: $a\cdot \frac{n}{2}=\frac{a}{2}n$ with $k=\frac{a}{2}<1$ ✓) ⟹ $T(n)=\Theta (n)$.
• $a=2$: ${\log }_{2}a=1$, tie ⟹ Case 2 ⟹ $T(n)=\Theta (n\log n)$.
• $a>2$: ${\log }_{2}a>1$, leaves bigger ⟹ Case 1 ⟹ $T(n)=\Theta (n^{{\log }_{2}a})$.
• The single transition point is $a=2$: below it the root dominates ($\Theta (n)$), exactly at it every level ties ($\Theta (n\log n)$), and above it the leaves dominate ($\Theta (n^{{\log }_{2}a})$).

• The tree has depth $L={\log }_{b}n$ (each step divides size by $b$ until size 1: $n/b^L=1$).
• Claim: level $i$ has $a^i$ nodes. Base $i=0$: one root, $a^0=1$ ✓. Step: if level $i$ has $a^i$ nodes and each spawns $a$ children, level $i+1$ has $a\cdot a^i=a^{i+1}$ ✓. By induction the claim holds for all $i$.
• Leaves sit at $i=L={\log }_{b}n$, so their count is $a^L=a^{{\log }_{b}n}.$
• Rewrite $a^{{\log }_{b}n}$ as $n^{{\log }_{b}a}$. Take the natural log of the left side: $\ln \left(a^{{\log }_{b}n}\right)=({\log }_{b}n)(\ln a)=\frac{\ln n}{\ln b}\ln a$. Take the natural log of the right side: $\ln \left(n^{{\log }_{b}a}\right)=({\log }_{b}a)(\ln n)=\frac{\ln a}{\ln b}\ln n$. Both equal $\frac{\ln a\ln n}{\ln b}$, and $\ln$ is one-to-one, so the original quantities are equal: $a^{{\log }_{b}n}=n^{{\log }_{b}a}.$
• Hence the number of leaves is $n^{{\log }_{b}a}$. Each leaf does $\Theta (1)$ work, so total leaf work $=n^{{\log }_{b}a}\cdot \Theta (1)=\Theta (n^{{\log }_{b}a})$. This is exactly the watershed cost $n^{c_{\text{crit}}}$ from the parent note. ∎

• Keep $f$ in the same case for the whole range. Take $f(n)=n^3$ and $b=2$, so $c_{\text{crit}}={\log }_{2}a$ ranges from $0$ (at $a=1$) up to $3$ (at $a=8$).
• To keep $f(n)=n^3$ strictly the dominant term we need $c_{\text{crit}}<3$, i.e. ${\log }_{2}a<3$, i.e. $a<8$. So for $a\in \{1,\dots ,7\}$: $f=n^3$ is polynomially larger than $n^{c_{\text{crit}}}$ ⟹ Case 3 ⟹ $T(n)=\Theta (n^3)$, independent of $a$.
• Why unchanged: in Case 3 the root work $f(n)$ dominates the whole sum; the number of subproblems only affects the (geometrically smaller) lower levels, which collapse into the constant. Increasing $a$ within the root-heavy regime does not touch the asymptotics.
• So the student is wrong: $a$ matters only when it pushes you across a case boundary (here, reaching $a=8$ where $c_{\text{crit}}=3$ ties $f$ and flips to Case 2, $\Theta (n^3\log n)$).

The leaf exponent is ==$c_{\text{crit}}={\log }_{b}a$==. Master Theorem's plain three cases fail when the gap between $f(n)$ and $n^{c_{\text{crit}}}$ is only logarithmic (not polynomial). Case 3 requires the extra regularity condition $af(n/b)\le kf(n)$ with $k<1$.