title: Is incrementing in a loop exponential time?
body: <p>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 <em>loop</em>, like this:  </p>
  
  <pre><code>int input,output=0;
  cin &gt;&gt; input;
  while (input--) ++output; // Takes time proportional to the value of input
  cout &lt;&lt; output;
  </code></pre>
  
  <p>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. </p>
  
  <p>Is this reasoning right?</p>