Is incrementing in a loop exponential time?
- by user356106
I've a simple but confusing doubt about whether the program below runs in exponential time. The question is : given a +ve integer as input, print it out. The catch is that you deliberately do this in a loop, like this:
int input,output=0;
cininput;
while(input--) ++output; // Takes time proportional to the value of input
cout<< output;
I'm claiming that this problem runs in exponential time. Because, the moment you increase the # of bits in input by 1, the program takes double the amount of time to execute. Put another way, to print out log2(input) bits, it takes O(input) time.
Is this reasoning right?
