Expert: Zlatko - 5/10/2011

Question
Hi Zlatko,

Could you please tell me how to find the time complexity of a given c program??

Please suggest me best short cut to find time complexity.

For Example -
Question: Find the time complexity of the following c program:
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
 t=a[j];
 a[j]=a[j+1];
 a[j+1]=t;
 }
}


Thanks in advance.

-Best Wishes
Manu Thakur

Answer
Hello Manu Thakur

The time complexity is a measure of how the execution time varies with the amount of data to be processed. In your example, the amount of data to be processed is indicated by n. In your example you have two nested loops.

In its first time through, the inner loop runs n-1 times (j going from 0 up to, but not including n-1). The second time through, it runs n-2 times, then n-3 times, and so on until, on the last entry of the inner loop, when i is n-2, and inner loop runs only once. So the instructions inside the inner loop are executed n-1 + n-2 + n-3 + ... + 1 times. This is close enough to the sum of all numbers from 1 to n that we can use the formula for that sum. The sum of all numbers from 1 to n is (n^2 + n)/2. When finding the time complexity, we focus on the highest order term only, and ignore all constants. In this case we focus only on the n^2 term and the time complexity of this algorithm is O(n^2). This means that the time to process the data varies as the square of the amount of data. You can see that we are not looking for some exact number, only a general trend, which is why it is ok to approoximate the sum from 1 to n-1 using the formula for the sum of 1 to n.

I don't know of any shortcuts. You need to use your mind to analyse the code. Sometimes the code will be too complex to analyse. In that case you need to do experiments with various data set sizes, and try to find a relationship between the processing time and the data set size.

The topic of algorithm analysis is deep and broad. I hope this answer has helped you understand a small part of it.

Best regards
Zlatko