A while loop time complexity

Question

I'm interested in determining the big O time complexity of the following:

def f(x):
    r = x / 2
    d = 1e-10
    while abs(x - r**2) > d:
        r = (r + x/r) / 2
    return r

I believe this is O(log n). To arrive at this, I merely collected empirical data via the timeit module and plotted the results, and saw that a plot that looked logarithmic using the following 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')

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?

It's not actually dividing by 2, because it's first increasing it by x/r. When x=10, the values of r are 5.0 3.5 3.178571428571429 3.162319422150883 3.1622776604441363 3.162277660168379 — Barmar
– Barmar, Commented May 29, 2020 at 21:40

Garrigan Stafford · Accepted Answer · 2020-05-29 22:11:56Z

This is Heron's (Or Babylonian) method for calculating the square root of a number. https://en.wikipedia.org/wiki/Methods_of_computing_square_roots

Big O notation for this requires a numerical analysis approach. For more details on the analysis you can check the wikipedia page listed or look for Heron's error convergence or fixed point iteration. (or look here https://mathcirclesofchicago.org/wp-content/uploads/2015/08/johnson.pdf)

Broad-strokes, if we can write the error e_n = (x-r_n**2) in terms of itself to where e_n = (e_n**2)/(2*(e_n+1))

Then we can see that e_n+1 <= min{(e_n**2)/2,e_n/2} so we have the error decrease quadratically. With the degrees of accuracy effectively doubling each iteration.

Whats different between this analysis and Big-O, is that the time it takes does NOT depend on the size of the input, but instead of the wanted accuracy. So in terms of input, this while loop is O(1) because its number of iterations is bounded by the accuracy not the input.

In terms of accuracy the error is bounded by above by e_n < 2**(-n) so we would need to find -n such that 2**(-n) < d. So log_2(d) = b such that 2^b = d. Assuming d < 2, then n = floor(log_2(d)) would work. So in terms of d, it is O(log(d)).

EDIT: Some more info on error analysis of fixed point iteration http://www.maths.lth.se/na/courses/FMN050/media/material/part3_1.pdf

Barmar · Accepted Answer · 2020-05-29 22:10:51Z

I believe you're correct that it's O(log n).

Here you can see the successive values of r when x = 100000:

(I've rounded them off because the fractions are not interesting).

What you can see if that it goes through two phases.

Phase 1 is when r is large. During these first few iterations, x/r is tiny compared to r. As a result, r + x/r is close to r, so (r + x/r) / 2 is approximately r/2. You can see this in the first 8 iterations.

Phase 2 is when it gets close to the final result. During the last few iterations, x/r is close to r, so r + x/r is close to 2 * r, so (r + x/r) / 2 is close to r. At this point we're just improving the approximation by small amounts. These iterations are not really very dependent on the magnitude of x.

Here's the succession for x = 1000000 (10x the above):

This time there are 10 iterations in Phase 1, then we again have 4 iterations in Phase 2.

The complexity of the algorithm is dominated by Phase 1, which is logarithmic because it's approximately dividing by 2 each time.

Collectives™ on Stack Overflow

A while loop time complexity

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related