title: What is the time complexity of this multiplication algorithm?
body: <p>For the classic interview question "How do you perform integer multiplication without the multiplication operator?", the easiest answer is, of course, the following linear-time algorithm in C:</p>
  
  <pre><code>int mult(int multiplicand, int multiplier)
  {
      for (int i = 1; i &lt; multiplier; i++)
      {
          multiplicand += multiplicand;
      }
  
      return multiplicand;
  }
  </code></pre>
  
  <p>Of course, there is a faster algorithm. If we take advantage of the property that bit shifting to the left is equivalent to multiplying by 2 to the power of the number of bits shifted, we can bit-shift up to the nearest power of 2, and use our previous algorithm to add up from there. So, our code would now look something like this:</p>
  
  <pre><code>#include &lt;math.h&gt;
  
  int log2( double n )
  {
      return log(n) / log(2);
  }
  
  int mult(int multiplicand, int multiplier)
  {
      int nearest_power = 2 ^ (floor(log2(multiplier)));
      multiplicand &lt;&lt; nearest_power;
      for (int i = nearest_power; i &lt; multiplier; i++)
      {
          multiplicand += multiplicand;
      }
  
      return multiplicand;
  }
  </code></pre>
  
  <p>I'm having trouble determining what the time complexity of this algorithm is. I don't believe that <code>O(n - 2^(floor(log2(n))))</code> is the correct way to express this, although (I think?) it's technically correct. Can anyone provide some insight on this?</p>