Master Theorem

*The content is based on 2022 Fall EE205 MasterMethod Lecture.

 

Master Method is a powerful black box for solving recurrences such as Divide and Conquer Method.

Assumption: All subproblems have equal size.  

$T\left(n\right)$ is the function to analyze operation costs to solve problem size of $n$.

 

Settings

1. Base Case: $\forall$ sufficeiently small $n$,  $T\left(n\right) \le$ a constant 

2. Recurrence: $\forall$ larger $n$,  $T\left(n\right) \le a T\left(\frac{n}{b}\right)+O\left({n}^{d}\right)$

where $a,b,d$ are integers that satisfy $a \ge 1,\ b \ge 2,\ d \ge 0$

$a$: number of next subproblem branches for each subproblem.

$b$: input size shrink factor

$d$: exponent in running time of combining step

 

Theorem

$T\left(n\right) \le a T\left(\frac{n}{b}\right)+O\left({n}^{d}\right)$

 

$T\left(n\right) =
\begin{cases}O\left({n}^{d}log {n}\right), & \mbox{if }a={b}^{d}\quad\mbox{(Case 1)} \\
O\left({n}^{d}\right), & \mbox{if }a<{b}^{d}\quad\mbox{(Case 2)} \\
O\left({n}^{log_{b}{a}}\right), & \mbox{if }a>{b}^{d}\quad\mbox{(Case 3)}
\end{cases}$

 

Examples

Merge Sort

$T(n) = 2T(\frac{n}{2})+O(n^1)$

$a=2,b=2,d=1$

$a=b^d$ => Case 1

$T(n) = O(n^d log \ n) = O(n log n)$

 

Karatsuba Integer Multiplication

$T(n) = 3T(\frac{n}{2})+O(n^1)$

$a=3,b=2,d=1$

$a>b^d$ => Case 3

$T(n) = O(n^{d} log_{b}{a}) = O(n^{log_{b}{a}})$

 

Random Slow Divide and Conquer Algorithm

$T(n)=2T(\frac{n}{2})+O(n^2)$

$a=2,b=2,d=2$

$a<b^d$ => Case 2

$T(n)=O(n^d)=O(n^2)$

 

Proof

It uses recursion tree and it's straightforward with geometrical series. 
https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/mm-proof.pdf

 

Interpretation

Case 1: Same amount of work each level

=> expect $O(n^{d}log{n})$

 

Case 2: Less work at next level

=> most work at the root

=> expect $O(n^d)$

 

Case 3: More work at next level

=> most work at the leaves

=> expect $O(a^{log_{b}{n}})
= O(n^{log_{b}{a}})$