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