[FIXED] Why do these two square root algorithms run so differently though they should work exactly the same?

Issue

I was coding on python, learning computer science, and I decided to try solving one of the questions that were being explained before seeing the solution code.

However, the solution code that I wrote, although it works fine, takes 50813497 iterations (that's nearly 51 million) to compute the square root of 49, whereas the code that is given in the solution takes only 54 iterations to achieve the same.

Here's my code:

def ssqrt(x):
    origx = x
    epsilon = 0.000001
    num_guess = 0
    while abs((x/2)**2 - origx) >= epsilon:
        #print(x)
        num_guess+=1
        if (x/2)**2 >= origx:
            x = x/2
        elif (x/2)**2 <= origx:
            x = (3/2)*x

    if abs((x/2)**2 - origx) < epsilon:
        print(num_guess)    
        return x/2
y = ssqrt(49)
print(y)

And here's the solution code:

x = 49
low = 0
high = x
ans = (low+high)/2
epsilon = 0.00000000000001
num = 0
while abs(ans**2-x) >= epsilon:
    num += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans
    ans = (high+low)/2
print (num)
print (ans)

Now, I understand that mine is a function and that the code given in the solution is not a function, but the overall idea is that we're trying to implement a bisection search algorithm. That's what I'm trying to get at.

Do please help out.

(FYI, this was being taught in the edX course, Introduction to Computer Science and Programming Using Python)

Solution

Further explaining what @Jkind9 said, the given solution uses binary search which halves the search space each iteration, thus executing with logarithmic run-time. If the search space for one binary iteration is [low, high], the search space for the next iteration will be either [low, (low + high) / 2] or [(low + high) / 2, high], effectively halving the number of elements that need to be observed in future iterations. Combining this with the fact that only one element (the middle element) is examined each iteration, the run-time of binary search is thus O(log2 n), where n is the number of elements to search for.

Your algorithm, however, does not halve the search space each time; you simply search through the exact same range on average. Reinterpreting your algorithm in a binary search-like way (with a lower and upper bound), the search space of every iteration can be considered as [0, x] (let n be the number of numbers to check in this range), where x / 2 is the element that is examined each iteration. The next iteration will have a search space of either [0, x/2] (n/2 numbers) or [0, 3x/2] (3n/2 numbers). The next iteration will thus have a search space of (n/2 + 3n/2)/2 = n numbers on average, giving your algorithm a linear time complexity on average (The actual number of iterations taken could be more or less depending on the input and what path the algorithm takes in the branch).

This can also be verified by using the inputs to find the number of iterations; when your algorithm is tasked to find the square root of 49 with an epsilon of 0.000001, it has to look through roughly 49 / 0.000001 = 49,000,000 numbers to find the right one. If the average time complexity of the algorithm is O(n), it is reasonable to estimate that it will take around 49,000,000 iterations on average to find this square root. The number of iterations actually taken is 50,813,497, which is not very far from our estimate (relative error: 3.7%). Similarly , with the given epsilon the binary search algorithm has to look through roughly 4.9e15 numbers. Given that the time complexity of binary search is O(log2 n), the number of iterations taken should be ceil(log2(4.9e15)) = 53, which is again very close to the number of iterations actually taken (54).

Answered By - EvilTak