Introduction to DAA

Master Theorem - General form of recurrance relation\(\(T(n)\ = \ aT(\frac{n}{b}) + f(n)\)\)\(\(f(n) \ = \ \theta(n^klog^pn)\)\)Where a >= 0 and b > 0

Cases
1.  If $log^a_b > k$ then $\theta(n^{log^a_b})$
2.  If $log^a_b = k$ then
    1. if p > -1 then $\theta(n^klog^{p+1}n)$
    2. if p = -1 then $\theta(n^kloglogn)$
    3. if p < -1 then $\theta(n^k)$
3. if $log^a_b < k$ then
    1. if p >= 0 $\theta(n^klog^pn)$
    2. if p < 0 then $\theta(n^k)$