Is incrementing in a loop exponential time?

Posted by user356106 on Stack Overflow See other posts from Stack Overflow or by user356106
Published on 2010-06-02T07:17:35Z Indexed on 2010/06/02 7:24 UTC
Read the original article Hit count: 240

Filed under:

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;
cin>>input;
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?

© Stack Overflow or respective owner

Related posts about algorithm-design