Monday, June 30, 2014

Time Complexity - Linear, Polynomial and Exponential

Whenever I discuss about the complexity of programs, most of the times, I drain all my energy in few minutes (because of talking in very loud voice). The following example is very famous.

Is it linear, polynomial or exponential?

calculate(int c, int n)
   BigInteger x = 1;
   for(int i=0; i<n; i++) {
       x = x*c;
   return x;

If I am giving input, and you are calculating output, then

Linear - You spend roughly equal amount of time as me
Polynomial - You spend significantly more amount of time than me, but, you will do it.
Exponential - I spend couple of mins, and your whole life is not enough to calculate the output.

If anyone says the above program is linear or polynomial, I am ready to spend 10 seconds of my time in giving the input. Are you ready to calculate the output?

No comments:

Post a Comment