divide-and-conquer

Solving Divide-and-Conquer Recurrences

Overview

Use this skill when the hard part is choosing the correct recurrence tool, not merely simplifying algebra.

Core principle: identify the recurrence shape and theorem preconditions before applying a canned case. If the preconditions fail, switch methods instead of forcing the theorem.

Shared CLRS Conventions

Follow the parent clrs skill for mathematical formatting, formula-free headings, direct polished answers, and CLRS-wide answer style.

When to Use

• An algorithm divides a problem of size $n$ into subproblems and combines their answers.
• You need a tight bound for $T(n)$ using substitution, a recursion tree, Master theorem, or Akra-Bazzi.
• A prompt suggests a shortcut such as “just use Master theorem” or “ignore the unequal split.”
• You need to compare standard recursive matrix multiplication with Strassen’s algorithm.

Do not use this skill for nonrecursive loop counting unless a recurrence is the central model.

Method Selection

Recurrence shape	First method to try	Watch for
$T(n)=aT(n/b)+f(n)$	Master theorem	Polynomial separation and regularity
Unequal subproblems, such as $T(n/3)+T(2n/3)+f(n)$	Akra-Bazzi or recursion tree	Classical Master theorem does not apply
Nonstandard argument, such as $T(\sqrt n)$	Change variables first	Apply Master theorem to the new variable
Bound proof requested	Substitution	Use explicit constants, not asymptotic notation in the inductive hypothesis
Matrix multiplication recurrence	Master theorem or recursion tree	Branching factor drives the exponent

Master Theorem Checklist

For $T(n)=aT(n/b)+f(n)$ with $a>0$ and $b>1$, compare $f(n)$ to the watershed $n^{\log_b a}$.

1. If $f(n)=O(n^{\log_b a-\epsilon})$ for some $\epsilon>0$, then $T(n)=\Theta(n^{\log_b a})$.
2. If $f(n)=\Theta(n^{\log_b a}\lg^k n)$ for constant $k\ge0$, then $T(n)=\Theta(n^{\log_b a}\lg^{k+1}n)$.
3. If $f(n)=\Omega(n^{\log_b a+\epsilon})$ for some $\epsilon>0$ and $af(n/b)\le cf(n)$ for some $c<1$ and sufficiently large $n$, then $T(n)=\Theta(f(n))$.