Is incrementing in a loop exponential time?

Question

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?

Answer 1

You have kind of answered your own question:

// Takes time proportional to the value of input

This is exactly what happens. If you double the input you double the time taken. If you triple it you triple time taken.

ie. cost = constant * input_size

Which you can see is a linear relationship for input_size.

An exponential relationship would be something like:

cost = constant * (input_size)^x

Where it is X you vary. This is not the case here.

Answer 2

I think where you are a bit confused is when you reason:

the moment you increase the number of bits in input by 1, the program takes double the amount of time to execute

This is effectively saying that when you double the size of the input, the execution time doubles. Thus, it is actually a linear relationship and would be Big O(n).

Answer 3

You could say it's exponential, but it still ends up being O(input) in the end.

The size of the input is O(log input). As you said, doubling the value doubles the time:

1 bits => 1 increments max
2 bits => 4 increments max
3 bits => 8 increments max
...
n bits => 2^n increments max

So the running time is O(2^log(input)) = O(input). So you could say it's exponential in the number of bits or linear in the value. It's the same thing. Usually you say it's linear in the value of input though.