# Master Theorem

Learned in CS341.

Theorem (Master theorem)

Suppose that $a≥1$ and $b>1$. Consider the recurrence $T(n)=aT(bn )+Θ(n_{y})$ in sloppy or exact form. Denote $x=g_{b}a$. Then

\ \end{cases}$$

Learned in CS341.

Theorem (Master theorem)

Suppose that $a≥1$ and $b>1$. Consider the recurrence $T(n)=aT(bn )+Θ(n_{y})$ in sloppy or exact form. Denote $x=g_{b}a$. Then

\ \end{cases}$$