title: Time complexity of this for loop: for (i = 2; i < N; i = i * i)?
body: <p>We're learning about time complexity right now and I'm having a ton of trouble with this one example. </p>
  
  <pre><code>for (i = 2; i &lt; n; i = i * i)
  {
       ... do something ...
  }
  </code></pre>
  
  <p>The prof said that it was O(sqrt(N)), but I'm not sure that I'm convinced. After all, if N=16, it only runs 2 times, not 4 right?</p>
  
  <p>My approach to solution:
  2^(2k) = N, where k is the number of times the loop runs.
  Removing the constant factors, k runs log(N) times.
  Where am I going wrong here? Thanks for any advice on the matter.</p>