Recurrence Relations - Applications

The Master Theorem is a powerful tool for analyzing divide-and-conquer algorithms, providing asymptotic solutions to a broad class of recurrence relations without requiring detailed calculation.

DefinitionMaster Theorem

Let $a \geq 1$ and $b > 1$ be constants, and let $f(n)$ be a function. Consider the recurrence: $T(n) = aT(n/b) + f(n)$

where we interpret $n/b$ as either $\lfloor n/b \rfloor$ or $\lceil n/b \rceil$ . Then:

Case 1: If $f(n) = O(n^c)$ where $c < \log_b a$ , then $T(n) = \Theta(n^{\log_b a})$ .

Case 2: If $f(n) = \Theta(n^c \log^k n)$ where $c = \log_b a$ and $k \geq 0$ , then $T(n) = \Theta(n^c \log^{k+1} n)$ .

Case 3: If $f(n) = \Omega(n^c)$ where $c > \log_b a$ , and if $af(n/b) \leq kf(n)$ for some constant $k < 1$ and sufficiently large $n$ (regularity condition), then $T(n) = \Theta(f(n))$ .

Intuition:

The recurrence $T(n) = aT(n/b) + f(n)$ describes an algorithm that:

Divides a problem of size $n$ into $a$ subproblems of size $n/b$
Performs $f(n)$ work to divide and combine

The recursion tree has height $\log_b n$ (depth of recursion) and $a^i$ nodes at level $i$ , each with work $f(n/b^i)$ .

Total work: $\sum_{i=0}^{\log_b n - 1} a^i f(n/b^i) + \Theta(n^{\log_b a})$

The three cases compare $f(n)$ with $n^{\log_b a}$ (the number of leaves):

Case 1: Leaf-dominated: most work is in base cases
Case 2: Balanced: work is evenly distributed across levels
Case 3: Root-dominated: most work is in dividing/combining

Proof Sketch (Case 1):

Assume $f(n) = O(n^c)$ where $c < \log_b a$ . Let $\epsilon = \log_b a - c > 0$ .

At level $i$ of the recursion tree, there are $a^i$ nodes, each doing $f(n/b^i) \leq C(n/b^i)^c$ work.

Total work at level $i$ : $a^i \cdot C(n/b^i)^c = Cn^c \cdot (a/b^c)^i$

Since $c < \log_b a$ , we have $a/b^c > 1$ , so work increases geometrically with depth.

Summing over all $\log_b n$ levels: $T(n) = \sum_{i=0}^{\log_b n - 1} Cn^c(a/b^c)^i + \Theta(n^{\log_b a})$

The geometric series is dominated by its last term, which is $O(n^c \cdot (a/b^c)^{\log_b n}) = O(n^{\log_b a})$ .

Therefore, $T(n) = \Theta(n^{\log_b a})$ . $\square$

ExampleCommon Applications

Merge Sort: $T(n) = 2T(n/2) + \Theta(n)$

Here $a = 2$ , $b = 2$ , $f(n) = \Theta(n)$ , so $\log_b a = 1$
Case 2 with $k = 0$ : $T(n) = \Theta(n \log n)$

Binary Search: $T(n) = T(n/2) + \Theta(1)$

Here $a = 1$ , $b = 2$ , $f(n) = \Theta(1)$ , so $\log_b a = 0$
Case 2 with $k = 0$ : $T(n) = \Theta(\log n)$

Strassen's Matrix Multiplication: $T(n) = 7T(n/2) + \Theta(n^2)$

Here $a = 7$ , $b = 2$ , $f(n) = \Theta(n^2)$ , so $\log_b a = \log_2 7 \approx 2.807$
Case 1 since $2 < 2.807$ : $T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})$

Remark

The Master Theorem doesn't cover all recurrences. For instance, $T(n) = 2T(n/2) + n \log n$ falls in the gap between Cases 2 and 3. The Akra-Bazzi method generalizes to handle variable partition sizes and more complex combining costs. For recurrences with multiple recursive calls of different sizes (like $T(n) = T(n/3) + T(2n/3) + n$ ), more sophisticated analysis or the Akra-Bazzi method is required.