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
algorithm-design
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