Question bank — Divide and conquer — template, correctness, recurrence

False. $a$ sits in the exponent ${\log }_{b}a$, so raising $a$ raises the leaf cost $n^{{\log }_{b}a}$. Karatsuba wins precisely by dropping $a$ from 4 to 3, not by adding subproblems.

False. Correct parts only give a correct whole if the combine step is itself correct — that is a separate proof obligation (e.g. merge in Mergesort needs its own loop-invariant argument).

True. The recursion tree is more general; the Master Theorem is a shortcut that only applies when $f(n)$ is polynomially above/below $n^{{\log }_{b}a}$, so it fails on gaps like $f(n)=n\log n$ over $n^1$.

True. The base case is the induction base, the recursive calls invoke the inductive hypothesis on smaller sizes, and combine-correctness is the inductive step — the recursion tree is the induction tree.

False. $f(n)$ is the non-recursive work only — divide plus combine. The recursive work is captured by the $aT(n/b)$ term, kept separate so we can unroll it.

False. It also needs the regularity condition $af(n/b)\le kf(n)$ for some $k<1$; without it a fast-growing but wildly oscillating $f$ can escape Case 3.

True. Binary Search has $c_{\text{crit}}={\log }_{2}1=0$ with $f=\Theta (n^0)$, and Mergesort has $c_{\text{crit}}=1$ with $f=\Theta (n^1)$ — in both, $f$ matches the leaf cost, giving the extra $\log n$ factor.

False. A constant threshold only changes constants and low-order terms; the Big-O class stays the same, though it can help real-world constants.

True. If subproblems overlap and get re-solved, you are in Dynamic Programming territory instead; pure D&C assumes the pieces don't share sub-work.

Error: no progress. One branch still has size 1, so it never shrinks — infinite recursion. Every recursive call must have strictly smaller size, which forces an explicit base case.

Error: $f$ is only a logarithmic factor above $n^1$, not polynomially above — so Case 3 does not apply. The recursion tree gives $\Theta (n{\log }^{2}n)$.

Error: you cannot just multiply $f$ by $a$. Here $c_{\text{crit}}={\log }_{2}3\approx 1.585>1$, so $f$ is below the leaf cost → Case 1 → $\Theta (n^{{\log }_{2}3})$.

Error: incomplete proof. You still owe progress (every call strictly smaller) and base correctness (smallest cases right). Missing either breaks both proof and code.

Error: with $a=1$ the tree is a single chain of height ${\log }_{2}n$, each node doing $\Theta (1)$ → total $\Theta (\log n)$, not $\Theta (1)$.

Error: Strassen does only 7 multiplies ($a=7,b=2$), so $c_{\text{crit}}={\log }_{2}7\approx 2.807$ and $T(n)=\Theta (n^{2.807})$ — strictly below $n^3$.

Because for the recurrence we only care about the total non-recursive work per call; separating them adds no information but clutters the analysis.

There are ${\log }_{b}n$ levels, and each level multiplies the node count by $a$, giving $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ leaves — the branching factor $a$ dictates the exponent.

Because "shrinking" is only guaranteed if you prove strict progress; a bad split can stall at a fixed size, and without a return-without-recursing rule the stack overflows.

$a$ lives in the exponent ${\log }_{b}a$, which controls the polynomial degree of the runtime; shaving $f$ only changes lower-order terms once you're leaf-dominated.

Because the answer also depends on $f(n)$ relative to $n^{{\log }_{b}a}$ — a cheaper or costlier combine can push you into a different Master Theorem case.

Recursion re-invokes the same procedure on smaller inputs, which is exactly the shape of an inductive hypothesis "assume it works for size $<n$" — the tool matches the structure.

It is $\Theta (1)$ by definition — this is the base case, answered directly without recursion, and it anchors the whole induction.

The "tree" degenerates to a chain of height ${\log }_{b}n$; there is no leaf explosion, so cost is driven purely by the sum of $f$ down that chain (e.g. Binary Search → $\Theta (\log n)$).

It is negative (or, when $a=1$, zero); it signals the recursion shrinks work faster than it branches, so $f(n)$ almost always dominates and you fall into Case 3.

The clean Master Theorem no longer applies; you use the recursion-tree method or Akra–Bazzi, and unbalanced splits can degrade Quicksort toward $\Theta (n^2)$ in the worst case.

$f$ is polynomially above the leaf cost → Case 3 → $T(n)=\Theta (n^2)$; the root's combine work dominates the entire tree.