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?
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

simplycoderFirst 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 pseudocode for the oblivioussort algorithm is something like :
n is the length of the array.
OBVILIOUSSORT 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.
ii++ 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.
jj++ will run n1 times
so the net cost for 2nd for loop alone is 1+n+n1 = 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+21 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.
You are reading an archived discussion.
Related Posts
Indian cyber gaming championship 2011 is kicking off next week in Goa @ Palmarinha Resort — Porbvaddo, Calangute, Bardez. The games have been divided in following categories 
Team Games...
The 8 queens problem is a situation where we have to place 8 chess queens on an 8×8 chessboard such that no two queens attack each other i.e. no two...
currently,im doing 2nd year in electrial engineering......
plz give some key areas which i need to concentrate the most and which have more scope in future
thanq....
P.S: im new...
NPhard or Non Deterministic Polynomial Time Hard problem is a situation where an algorithm that solves it can be converted to one for solving other NPProblems.
It's also written that...
CrazyEngineers Free Mock Aptitude Test  5 On 21st August (Sunday) at 10:00 am
NOTICE: You must be CrazyEngineers Forum Member to participate in test. Those who do not have...