Solve Recurrence Relation using Master Theorem

Learn to solve recurrence relations and find asymptotic complexity of decreasing and dividing functions using master theorem. See online demo.

Master Theorem

Master theorem provides an asymptotic analysis (using Big O notation) for recurrence relations that occur in the analysis of many divide and conquer algorithms. The approach was first presented by Jon Bentley, Dorothea Haken, and James B. Saxe in 1980, where it was described as a "unifying method" for solving such recurrences. The name "master theorem" was popularized by the widely used algorithms textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.

Divide and Conquer

Let a ≥ 1 and b > 1 be constants, let f(n) be a function, and let T(n) be a function over the positive numbers defined by the recurrence
T(n) = aT(n/b) + f(n) where

a ≥ 1,
b > 1, and
f(n) = Θ(n^k log^p n), where k ≥ 0 and p ≥ 0

Case 1: If log_b a > k then Θ(n^{log_b a})

Case 2: If log_b a = k then

if p > -1 then Θ(n^k log^p+1 n)
if p = -1 then Θ(n^k log log n)
if p < -1 then Θ(n^k)

Case 3: If log_b a < k then

if p > 0 then Θ(n^k log^p n)
if p ≤ 0 then Θ(n^k)

Decrease and Conquer

Let a > 0 and b > 0 be constants, let f(n) be a function, and let T(n) be a function over the positive numbers defined by the recurrence
T(n) = aT(n - b) + f(n) where

a > 0,
b > 0, and
f(n) = Θ(n^k log^p n), where k ≥ 0 and p ≥ 0

Case 1: If a < 1 then Θ(f(n)) = Θ(n^k log^p n)

Case 2: If a = 1 then Θ(n * f(n)) = Θ(n^k+1 log^p n)

Case 3: If a > 1 then Θ(a^n/b * f(n)) = Θ(a^n/b n^k log^p n)