ForgotMyCode

Advanced Algorithm Analysis

Master theorem is a tool that can be used for analysis of certain recursive algorithms, especially the divide & conquer kind.

If we can express the algorithm using the following relation, Master theorem is appliable.

\[T(n) = a T(\frac{n}{b}) + f(n)\]

Just to be clear, the $\frac{n}{b}$ usually means $\left \lfloor \frac{n}{b} \right \rfloor$ or $\left \lceil \frac{n}{b} \right \rceil$.

Then,

If $f(n) \in O(n^{\textup{log}_ {b} a-\varepsilon })$ for some $\varepsilon > 0$, then $T(n) \in \Theta(n^{\textup{log}_ {b} a})$.
If $f(n) \in \Theta(n^{\textup{log}_ {b} a} \textup{log}^{k} n)$ for some $k \geq 0$, then $T(n) \in \Theta(n^{\textup{log}_ {b} a}\textup{log}^{k+1}n)$.
If $f(n) \in \Omega(n^{\textup{log}_ {b} a+\varepsilon })$ for some $\varepsilon > 0$ and $af(\frac{n}{b}) \leq cf(n)$ for some $c < 1$ and all $n > n_{0}$ for some $n_{0}$, then $T(n) \in \Theta(f(n))$.

To prove concrete algorithm’s complexity using master theorem is as easy as finding all constants of respective case.

Here are various math hacks that may be useful during algorithm analysis:

For all $a > 1$ and all $b > 1$, $\textup{log}_ {a} n \in \Theta(\textup{log}_ {b} n)$.
$\textup{log}(n!) \in \Theta(n \textup{log} n)$.
For all $n \geq 1$, $n^{\frac{n}{2}} \leq n! \leq (\frac{n + 1}{2})^{n}$.
For non-decreasing function $f(n)$, if $f(\frac{n}{2}) \in \Theta(f(n))$, then $\sum_{i=1}^{n}f(i) \in \Theta(nf(n))$.

Try proving them.