In this post I am going to discuss how to calculate time complexity of the algorithms.Firstly I am going to take up a non-recursive,simple algorithm and then look at the recursive ones.
What can be simpler than an algorithm to add two numbers.The method Sum does it for us:
1.Sum(a,b)
2. s=a+b // c1*1
3. return s //c2*1
The comments indicates the total time required by the respective statements at run-time.c1 and c2 are the time required to process the statement.It depends upon the processor speed which may be different for different computers while the 1's is the number of times(i.e. frequency) ,the statement is executed. Hence , the total time required is c1+c2 which is equal to some constant c.In algorithimic notations we express this constant function as O(1).
Now lets look at another algorithm.This time,the sum of first n natural numbers.
1.Nat_Sum(n)
2. s=0 //c1*1
3. for i=1 to n //c2*n
4. s=s+i //c3*n
5. return s //c4*1
Now just count the total time required.Its c1+c4+n(c2+c3) which is equal to some other constants e1+e2(n).
Hence in Big O notation it is expressed as O(n) removing all constants.So it is linear algorithm.
Similarly when there are two nested loops, the time complexity is generally O(n^2).
We will look at the recursive algorithms in the next post.
What can be simpler than an algorithm to add two numbers.The method Sum does it for us:
1.Sum(a,b)
2. s=a+b // c1*1
3. return s //c2*1
The comments indicates the total time required by the respective statements at run-time.c1 and c2 are the time required to process the statement.It depends upon the processor speed which may be different for different computers while the 1's is the number of times(i.e. frequency) ,the statement is executed. Hence , the total time required is c1+c2 which is equal to some constant c.In algorithimic notations we express this constant function as O(1).
Now lets look at another algorithm.This time,the sum of first n natural numbers.
1.Nat_Sum(n)
2. s=0 //c1*1
3. for i=1 to n //c2*n
4. s=s+i //c3*n
5. return s //c4*1
Now just count the total time required.Its c1+c4+n(c2+c3) which is equal to some other constants e1+e2(n).
Hence in Big O notation it is expressed as O(n) removing all constants.So it is linear algorithm.
Similarly when there are two nested loops, the time complexity is generally O(n^2).
We will look at the recursive algorithms in the next post.
Hi codeKNIGHT,
ReplyDeletein fact the second piece of code that you analyzed isn't linear. It maybe linear on n, but in a theoretical point of view the function Nat_Sum(n) is exponential in the size of the input.
It receives a number n (~lg(n) bits) and takes O(n) operations to finish, and so, its complexity is O(2^|n|), thus exponential.
In this cases the algorithm is called a "pseudo-polynomial" algorithm.
Thanks for the nice blog.