4.3 Master theorem

Geometric sum: The sum 1 + α + α² + … + αⁿ = (αⁿ⁺¹ - 1)/(α - 1), if α ≠ 1.
As a function of n, this geometric sum has leading term

• 1/(1-α), if α < 1,
• n, if α = 1,
• αⁿ/(α - 1), if α > 1,

The three cases may also be expressed simply as &Theta(1), &Theta(n), and Θ(αⁿ), respectively.

Master Theorem [upper bound form]:
Given the recurrence T(n) ≤ aT(n/b) + cn^d, for some constant c,
let e = log_b(a). Then

• T(n) = O(n^d), if e < d,
• T(n) = O(n^dlog(n)), if e = d, and
• T(n) = O(n^e), if e > d.

Paraphrase: The exponent of n is whichever dominates: the non recursive work (n^d) or the total work at the deepest lever of recursion, a^log_b(n). But when these two are equal there is a log(n) factor.

Proof idea: Consider the work at each depth of recursive call and get a formula of the form n^d ∑^log_b(n) (a/b^d)ⁱ.

Master Theorem [lower bound form]:
Given the recurrence T(n) ≥ aT(n/b) + cn^d, for some constant c,
let e = log_b(a). Then

• T(n) = Ω(n^d), if e < d,
• T(n) = Ω(n^dlog(n)), if e = d, and
• T(n) = Ω(n^e), if e > d.

Master Theorem [codominant form]:
Given the recurrence T(n) = aT(n/b) + Θ(n^d), for some constant c,
let e = log_b(a). Then

• T(n) = Θ(n^d), if e < d,
• T(n) = Θ(n^dlog(n)), if e = d, and
• T(n) = Θ(n^e), if e > d.

In the codominant case, we may also say, T(n) is essentially n^{max(d, log_b(a))}. The "essentially" simply means that we are ignoring logarithmic factors.

The master theorem applies to divide and conquer algorithms. Some algorithms lead to recurrences of the form T(n) = aT(n-b) + Θ(n^d). These might be called "subtract and conquer" or "giant step, baby step" algorithms. There is a similar theorem addressing these in this attachment (which also has a restatement of the master theorem). master theorem