Calculate time complexity of any algorithm

Replies

• 

  simplycoder

  First of all, you should know the basic details of the program and must decide the case of time complexity.
  I will consider the worst case.Let us try and find out complexity of a oblivious sort algorithm:
  let us assume that array A[] contains reverse sorted(unsorted in worst case) list of integers.
  The pseudo-code for the oblivious-sort algorithm is something like :
  n is the length of the array.
  

  OBVILIOUS-SORT
   for(i=0;i  Now let us consider each aspect.
  
    1)Consider the first for loop:for(i=0;i : 
  
        i=0 will run only once.
  
        i
        i++ will run n times.
  
         so the net cost is 1+(n+1)+n = 2n+2
  
  
  
  2)Consider the 2nd for : for(j=0;j
  
    Also let us consider this individually,without taking the effect of previous for loop.
  
     j=0 will run only once.
  
     j
     j++ will run n-1 times 
  
    so the net cost for 2nd for loop alone is 1+n+n-1 = 2n
  
  
  
  3) Swapping is a linear time algorithm, it will run only once per iteration.
  
  
  
  However since both the loops are nested, the second for loop will run 2n+2-1 times.(last i++ will beak the first for loop). 
  
  Multiplying its own cost to that of first for loop.So,
  
  
  
  T(n)= (2n+1)(2n(1)).. cost of first for loop*(cost of second for loop*(cost of swap))
  
  T(n)=(2n+1)(2n)
  
  T(n)=4n[SUP]2[/SUP]+2n
  
  T(n)=O(n[SUP]2[/SUP]).
  
  
  
  So this obvilious sort has time complexity of O(n[SUP]2[/SUP]).
  
  
  
  This can be simplified:In asymtotic analysis, when we consider O notations, we never go for the lower order terms.
  
  O(n[SUP]2[/SUP])=4n[SUP]2[/SUP]+3n+2
  
  O(n[SUP]2[/SUP])=10n[SUP]2[/SUP]+50n
  
  so in both the cases, the final time complexity in terms of O is n[SUP]2[/SUP].
  
  the easiest way, is to look at the number of loops and the nested loop.
  
  in the above sort algorithms, there are 2 for loops and are nested which will run for n times each, hence the time complexity is n*n=n[SUP]2[/SUP].
  
  
  
  You can write a code based on this, and run this on asymtotic inputs at periodic intervals(100,200,300, till you get bored), and take the time required to complete the sorting procedure. Plot a graph (you can use MS Excel for it),you can see the obvious n^2 characteristics.
  
  -Thank you.