Proof of the Master Theorem. $(15$ points$)$ Now that we have practiced with the re$-$

cursion tree method, the iteration method, and the Master method. The Master Theorem

states that, suppose $T(n)=a*T(\frac{n}{b})+O(n^d),$ we have:

$T(n)=\{\begin{array}{ccc}O(n^{d}logn),& if& a=b^d\\ O(n^d),& if& a{b}^d\end{array}$

Prove that the Master Theorem is true by using either the recursion tree method or the

iteration method.

Answer:Now that we have practiced with the re$-$ cursion tree method, the iteration method, and the Master method. The Master Theorem states that, suppose T $($n$)=$ a $$ T $($n$/$b$)+$ O$($nd$),$ we have: $$O$($nd log n$),$ if a $=$ bd $$d d T$($n$)=$ O$($n$),$ ifa bd Prove that the Master Theorem is true by using either the recursion tree method or the iteration method.