title: A while loop time complexity
body: <p>I'm interested in determining the big O time complexity of the following: </p>
  
  <pre><code>def f(x):
      r = x / 2
      d = 1e-10
      while abs(x - r**2) &gt; d:
          r = (r + x/r) / 2
      return r
  </code></pre>
  
  <p>I believe this is O(log n). To arrive at this, I merely collected empirical data via the <code>timeit</code> module and plotted the results, and saw that a plot that looked logarithmic using the following code: </p>
  
  <pre><code>ns = np.linspace(1, 50_000, 100, dtype=int)
  ts = [timeit.timeit('f({})'.format(n), 
                      number=100, 
                      globals=globals()) 
        for n in ns]
  plt.plot(ns, ts, 'or')
  </code></pre>
  
  <p>But this seems like a corny way to go about figuring this out. Intuitively, I understand that the body of the while loop involves dividing an expression by 2 some number k times until the while expression is equal to d. This repeated division by 2 gives something like 1/2^k, from which I can see where a log is involved to solve for k. I can't seem to write down a more explicit derivation, though. Any help?  </p>