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.

Complexity Analysis

I am presenting simple comlexity analysis of algorithms for that I'll use Insertion sort algorithm:

Insertion sort algo:

Insertion Sort(Array A)


 for int j=2 to A.length{    // it will loop through for n times, cost= c1*n

  key=A[j]   // it will loop for n-1 times, cost= c2*(n-1)

  i=j-1;   // it will loop for n-1 times, cost= c3*(n-1)    

  while( i>0 && A[i]> key){  // depends on condition being true, cost= c4 *(∑ tj where j=2 to n)

  A[i+1]= A[i];   //cost= c5 *(∑ tj-1 where j=2 to n)

  i--;   // cost= c6 *(∑ tj-1 where j=2 to n)

 }

  A[i+1]=key;   // cost= c7 *(n-1)

}

where all c1,c2 etc are constants, so the total time to excute this algorothms would be:
T(n)= c1*n+ c2*(n-1)+ c3*(n-1)+c4 *(∑ tj where j=2 to n)+ c5 *(∑ tj-1 where j=2 to n)+ c6 *(∑ tj-1 where j=2 to n)+c7 *(n-1)

In the worst case the inner while loop will execute for each element and hence will sum up as:
(∑ tj-1 where j=2 to n) = 1+2+3+4+-------+n-1 =  n*(n-1)/2
that will be equal to n^2.

So  now T(n)= c1*n+ c2*(n-1)+ c3*(n-1)+c4 *(n^2)+ c5*(n^2)+ c6*(n^2)+c7 *(n-1)

and since n^2 is the maximum term , ignoring lower order terms will give us :
T(n)=O(n^2).

This approach is very useful in analysis of all the algorithms which uses loops and gives basic idea of how to derive complexity.
Post comments if you face any issue to analyze complexity or any problems in this method to follow.