Solving Recurrences: Recursion Trees, Substitution & Master Theorem

The Recursion Tree Geometric Series & The Watershed Function $n^{\log_b a}$

Consider the recurrence $T(n) = a\,T(n/b) + f(n)$ where $a \ge 1$ and $b > 1$ are constants. At depth $j$ of the recursion tree ($0 \le j \le \log_b n$), there are $a^j$ nodes, each solving a subproblem of size $n / b^j$ and performing $f(n / b^j)$ local work. Summing across all levels gives the exact total runtime:

$$T(n) = \Theta\left(n^{\log_b a}\right) + \sum_{j=0}^{\log_b n - 1} a^j f\left(\frac{n}{b^j}\right)$$

Here, the number of leaves at the bottom of the tree is $a^{\log_b n} = n^{\log_b a}$ (by the logarithmic identity $a^{\log_b n} = (b^{\log_b a})^{\log_b n} = n^{\log_b a}$). We call $n^{\log_b a}$ the watershed function. Comparing $f(n)$ to $n^{\log_b a}$ yields the three regimes of the Master Theorem (including the generalized polylogarithmic Case 2):

Visualizing the Three Master Theorem Work Profiles

The SVG diagram below contrasts the per-level work across depth $j \in [0, \log_b n]$ for Case 1 (expanding geometric series), Case 2 (constant rectangular column), and Case 3 (contracting geometric series).

Change of Variables for Non-Linear Recurrences

Some recurrences do not shrink by a constant divisor $n/b$, such as $T(n) = 2T(\sqrt{n}) + \log_2 n$ (which arises in van Emde Boas trees). By substituting $m = \log_2 n$ (so $n = 2^m$ and $\sqrt{n} = 2^{m/2}$) and defining $S(m) = T(2^m)$, the recurrence transforms into a standard Master Theorem form:

$$S(m) = 2S(m/2) + m \implies S(m) = \Theta(m \log m) \implies T(n) = \Theta(\log n \log \log n)$$

// C++20: Coarsened Divide-and-Conquer with L1-Cache Base Case (Eliminating 97% of Call Frames)
#include <algorithm>
#include <cstddef>
#include <span>

// Base case threshold: 32 int64_t elements = 256 bytes (4 L1 cache lines)
constexpr size_t kLeafThreshold = 32;

void insertionSortBase(std::span<int64_t> a) noexcept {
    for (size_t i = 1; i < a.size(); ++i) {
        int64_t key = a[i];
        size_t j = i;
        while (j > 0 && a[j - 1] > key) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = key;
    }
}

// Recurrence: T(n) = 2 T(n/2) + Theta(n), pruned at n <= 32
void coarsenedMergeSort(std::span<int64_t> a, std::span<int64_t> scratch) noexcept {
    const size_t n = a.size();
    if (n <= kLeafThreshold) {
        insertionSortBase(a); // Prunes bottom 5 levels of recursion tree!
        return;
    }
    const size_t mid = n / 2;
    coarsenedMergeSort(a.first(mid), scratch.first(mid));
    coarsenedMergeSort(a.subspan(mid), scratch.subspan(mid));

    // Skip merge if already ordered across boundary (Best-Case Theta(n))
    if (a[mid - 1] <= a[mid]) return;

    std::merge(a.first(mid).begin(), a.first(mid).end(),
               a.subspan(mid).begin(), a.subspan(mid).end(),
               scratch.begin());
    std::copy(scratch.begin(), scratch.begin() + n, a.begin());
}