Solving Recurrences & the Master Theorem

#1. The substitution method

Guess the form of the solution, then prove it by induction.

Example: T(n) = 2T(⌊n/2⌋) + n. Guess T(n) ≤ c·n log n.

Assume it holds for n/2: T(n/2) ≤ c(n/2)log(n/2). Then

T(n) ≤ 2·c(n/2)log(n/2) + n = c·n log n − c·n·log 2 + n = c·n log n − c·n + n ≤ c·n log n whenever c ≥ 1.

So T(n) = O(n log n).

#2. The recursion-tree method

Draw the tree of recursive calls, add the cost at each level, then sum the levels.

T(n) = 2T(n/2) + n:

Total = n × (log₂ n + 1) = Θ(n log n).

#3. The Master Theorem

For recurrences of the form

T(n) = a·T(n/b) + f(n), with a ≥ 1, b > 1

compare f(n) with n^(log_b a) (the total cost of the leaves):

#Worked examples

#Extended case 2

If f(n) = Θ(n^(log_b a) · logᵏ n) with k ≥ 0, then T(n) = Θ(n^(log_b a) · logᵏ⁺¹ n). For example, T(n) = 2T(n/2) + n log n = Θ(n log² n).

#When the Master Theorem does not apply

• Subproblems of different sizes: T(n) = T(n/3) + T(2n/3) + n (use a recursion tree: Θ(n log n)).
• Subtract-and-conquer forms: T(n) = T(n − 1) + n (unroll: Θ(n²)); T(n) = 2T(n − 1) + 1 (Θ(2ⁿ)).
• f(n) falls in a gap between cases, e.g. T(n) = 2T(n/2) + n/log n.
• a < 1 or b ≤ 1.

#Unrolling (iteration method)

For T(n) = T(n − 1) + n with T(1) = 1:

T(n) = n + T(n−1) = n + (n−1) + T(n−2) = … = n + (n−1) + … + 2 + 1 = n(n+1)/2 = Θ(n²).

#Check a solution by computing it

#include <cstdio>
#include <cmath>
#include <map>

std::map<long, double> memo;
double T(long n) {                       // T(n) = 2T(n/2) + n, T(1) = 1
    if (n <= 1) return 1;
    if (memo.count(n)) return memo[n];
    return memo[n] = 2 * T(n / 2) + n;
}

int main() {
    printf("%10s %14s %14s\n", "n", "T(n)", "T(n)/(n log n)");
    for (long n = 16; n <= (1L << 24); n *= 16)
        printf("%10ld %14.0f %14.4f\n", n, T(n), T(n) / (n * log2((double)n)));
    return 0;
}

         n           T(n) T(n)/(n log n)
        16             80         1.2500
       256           2304         1.1250
      4096          53248         1.0833
     65536        1114112         1.0625
   1048576       22020096         1.0500
  16777216      419430400         1.0417

The ratio T(n)/(n log n) settles towards 1, confirming Θ(n log n).