CrazyEngineers
  • Ankita

    Ankita

    MemberAug 17, 2011

    Calculate time complexity of any algorithm

    A question is always asked in viva and interviews : "How to calculate the time complexity of a given algorithm".

    One might say that why should we calculate it when there are tools available for it?
    For example, we have Analyze menu in VS Team Suite, NDepend etc..

    The most common metric for calculating time complexity is Big O notation.

    Could someone explain how to calculate time complexity in simple words?
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies
  • simplycoder

    MemberAug 18, 2011

    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<n;i++)
      {
       for(j=0;j<n-1;j++) 
        { 
          if(A[j+1]<A[j]) 
           { 
                Swap(j+1,j)
            }
        }
      }
      
    Now let us consider each aspect.
    1)Consider the first for loop:for(i=0;i<n;i++) :
    i=0 will run only once.
    i<n will run n+1 times.
    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<n-1j++)
    Also let us consider this individually,without taking the effect of previous for loop.
    j=0 will run only once.
    j<n-1 will run n times
    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.
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register