Master theorem for complexity analysis

Master theorem is used to analyze complexity of many problems in divide and conquer category.
Master theorem deals with recurrence relations in the form:

T(n)= aT(n/b)+f(n)
where:
n is size of original problem
a is number of sub-problems
n/b size of sub-problems(assuming sub-problems of equal size)

f(n) is the time required to conquer(dividing or merging) the sub-problems;

such as merging in merge sort or finding pivot in quick sort</em>

There are 3 cases to solve such kind of recurrences:
In each of three cases we compare f(n) with (n ^log_ba). Polynomially larger of these functions determines solution.

Case 1:
If f(n) = O( n^c ) where c < log_ba
then solution becomes T(n) = θ(n ^log_ba)

In first case, comparison states that (n ^log_ba) is larger than f(n),hence solution θ(n ^log_ba)

For example:
T(n) = 9T(n/3)+1000n²
a=9, b=3, f(n)=n² (leaving constant terms)
n ^log_ba = n ^log₃9 = n³ which is polynomially greater than n².
Hence solution T(n) = θ(n³)

Case 2:
 if f(n) = θ(n ^{log _b a} )
then solution becomes T(n) = θ(n ^log_ba logn)
In second case, comparison states that (n ^log_ba) is equal to f(n), we multiply f(n) by logarithmic factor hence solution θ(n ^log_ba logn)

For example:
T(n) = T(n/2)+c (Binary search)
a=1, b=2, f(n)=c (constant)
n ^log_ba = n ^log₂1 = n⁰ = 1 which is equal to f(n).
Hence solution T(n) = θ(logn)

Case 3:
if f(n) = Ω( n^c ) where c > log_ba
and it is also true that af(n/b) <= kf(n) for some constant k < 1,
and sufficiently large n.
then solution becomes T(n) = θ( f(n) )

In third case comparison states that (n ^log_ba) is smaller than f(n).
hence solution θ( f(n) )

For example:
T(n) = 2T(n/2)+10n² a=2, b=2, f(n)=n² (leaving constant terms)
n ^log_ba = n ^log₂2 = n which is polynomially smaller than n².
Hence solution T(n) = θ(n²)  

Facts :
Master theorem doesn't apply if function is not polynomially large enough to determine solution.
 eg : T(n) = 2T(n/2)+nlogn here a=2,b=2
f(n) = n logn;
n^log_ba = n;
so f(n) is greater than n^log_ba but not polynomially large enough, its large by a factor of logarithm hence can't determine solution.