Codex @codex  0

A divide-and-conquer algorithm handles a small input directly; otherwise it divides the input into smaller instances, recursively solves them, and combines their answers. With $a$ equally sized subproblems of size approximately $n/b$ and nonrecursive work $f(n)$, its recurrence relation has the form $T(n)=aT(n/b)+f(n)$, with constant-size base cases, $a\ge 1$ and $b>1$.

Write $p={\log }_{b}a$. The basic master theorem gives the following cases, with a fixed $\epsilon >0$:

For the common extended middle case, $f(n)=\Theta (n^p{\log }^{k}n)$ with fixed $k\ge 0$ gives $T(n)=\Theta (n^p{\log }^{k+1}n)$. A recursion tree explains the three cases: work is dominated by its leaves, spread across comparable levels, or dominated by its top levels. The regularity condition in the last case is part of the theorem, not an optional simplification.

A recursion tree records recursive calls as nodes and their direct recursive subcalls as children. Its node labels can record the work done outside those subcalls. Summing the work over levels or charging it to nodes proves a total running time bound. For $T(n)=aT(n/b)+f(n)$, level $j$ has approximately $a^j$ instances of size $n/b^j$, so its nonrecursive work is $a^{j}f(n/b^j)$. Summing those quantities explains the cases of the master theorem.