Master Theorem

There are 3 cases:

1. If $$f(n) = O(n^{log_ba})$$ then $$T(n) = \Theta(n^{log_ba})$$
2. If $$f(n) = \Theta(n^{log_ba})$$ then $$T(n) = \Theta(n^{log_ba} log(n))$$
3. If $$f(n) = \Omega(n^{log_ba})$$ then $$T(n) = \Omega(f(n))$$ If f(n) satisfies the regularity condition: $$a f(n/b) <= cf(n) where c<1$$

How to apply Master's Theorem:

$$ T(n) = a T(n/b) + f(n)

$$

1.Extract a, b, f(n) from a given recurrence

1. Determine $$n^{log_ba}$$
2. Compare f(n) and $$n^{log_ba}$$ asymptotically
3. Determine and apply appropriate Masters Theorem

NOTE: Masters Theorem is not applicable to the following test case:

$$T(n) = kT(n/k) + n log n$$