Master Theorem

Master Theorem is used to find running time for divide and conquer algorithms. It provides asymptotic analysis for recurrence relation of the form \(T(n) = a*T(n/b) + f(n)\), for constants \(a>=1\) and \(b > 1\).

Note: Master Theorem doesn’t have a solution when \(f(n)\) is smaller than \(n^{\log_{\substack{b}}a}\) but not polynomially smaller. Similarly, it fails when \(f(n)\) is larger than \(n^{\log_{\substack{b}}a}\) but not polynomially larger.

The Theorem is dealt, case by case:

Case 1: When \(f(n)\) is polynomially smaller than \(n^{\log_{\substack{b}}a}\), then \(n^{\log_{\substack{b}}a}\) dominates and running time complexity is \(\mathcal{O} (n^{\log_{\substack{b}}a})\).

Case 2: When \(f(n) = n^{\log_{\substack{b}}a}\), then running time complexity is \(\mathcal{O} (n^{\log_{\substack{b}}a}\log(n))\).

Case 3: When \(f(n)\) is polynomially larger than \(n^{\log_{\substack{b}}a}\), then \(f(n)\) dominates and running time complexity is \(\mathcal{O} (f(n))\).