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.
15.1k views

Related Posts

@Ankita Katdare · Aug 9, 2014

China's Jiuquan Satellite Launch Centre located in the Gobi desert about 1,600 km from Beijing, successfully launched the remote sensing satellite named Yaogan XX along with a Long March 4C...
4.9k views

@Dipika Chaudhary · Feb 12, 2017

Hey, I'm CSE student in 2nd year. I requires some topics of latest innovative & creative projects even it'll tough no matter , just give me some topics which would...
7k views

@Ankita Katdare · Dec 24, 2015

Airtel prepaid users in Mumbai and Delhi have been introduced with unrestricted validity plans for internet data usage. The plans vary for the consumers from both these cities. In Delhi,...
4.5k views

@kingatheek · Aug 10, 2009

hi, i am studying my b.e aeronautical... i need a quite a few good topics, so that i could successfully prepare and present my presentation...
10.4k views

@Ankita Katdare · Jun 6, 2010

What types of CMOS memories have you designed? What were their size? Speed? Configuration Process technology? What work have you done on full chip Clock and Power distribution? What process...
3.4k views