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.