Master Theorem

Learned in CS341.

Theorem (Master theorem)

Suppose that $a\ge 1$ and $b>1$. Consider the recurrence $T(n)=aT\left(\frac{n}{b}\right)+\Theta (n^y)$ in sloppy or exact form. Denote $x={\log }_{b}a$. Then

\ \end{cases}$$