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