CrazyEngineers Archive
Old, but evergreen and popular discussions on CrazyEngineers, presented to you in read-only mode.
@Ankita Katdare • 18 Aug, 2011 • 1 like
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?
@simplycoder • 18 Aug, 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.
16.6k views

Related Posts

@m.vivekanandan · Apr 13, 2012

why are we not using starters for small bulbs while we use it for tube lights???im intersted in knowing basics of electrical engg....
42.1k views

@Kaustubh Katdare · Feb 27, 2011

CEans, You've always had lots of questions related to summer internships, training and certifications. We found out that CE Forums already had tons of related queries distributed in various sections....
4.9k views

@Ankita Katdare · Feb 3, 2015

Yesterday evening one of my friend's mum called me up to ask if I can install WhatsApp on her old phone. I now have it and it's a Samsung Duos...
5.3k views

@Kaustubh Katdare · Nov 10, 2013

Following the leads by Airtel & Reliance Jio, Aircel could be the next mobile network operator in India to launch 4G services. The operator is currently testing the network in...
4.4k views

@Kaustubh Katdare · Aug 27, 2012

Every year, a large number of engineering students flock CrazyEngineers Forum looking for tips and tricks on how to prepare for campus recruitments. I thought of compiling an article to...
21.2k views