Wednesday, December 24, 2014

Time Complexity

If I am an organizer of Kaun Banega Crorepati, I will ask the following question as the last question.

What is the complexity of this? for(i=1; i<n; i++) print i;
A. Logarithmic
B. Linear
C. Polynomial
D. Exponential



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.

My input is 100000000000000000000000000000000000000.