CODEWITHSUNDEEP
algorithmasymptotic-complexity
hrazzer
hrazzer

Reputation: 79

What is the asymptotic complexity of this particular (bad) algorithm for computing the square root of a number?

Stumbled across a (terrible) algorithm for computing the square root of a number. Got into a small argument about the time complexity. I assert that the time complexity is O(n^2) because for n input, it will be multiplied n times. My friend asserts that the time complexity is actually O(n). Who is right and why?

def squareRoot(x):
if x<0:
    return "undefined"
elif x==0:
    return 0
for i in range(0,x):
    if(i*i)==x:
        return i

Upvotes: 3

Views: 100

Answers (3)

Jahangir Ali
Jahangir Ali

Reputation: 55

Lets us first see how this algo works.

In worst case, that is, x is not perfect square, and x is prime, the time complexity will be O(n).
In best case. that is the no. is perfect square, then it will be in order of SQRT(n).

Upvotes: 0

moreON
moreON

Reputation: 2008

First we need to know what the complexity of integer multiplication is.

For simplicity, we'll use the Schönhage–Strassen algorithm . The complexity is O(n log n log log n) for numbers with n digits.

Of course the number n actually has O(log n) digits, so to multiply numbers of value n, the time complexity is O(log n log log n log log log n)

There are n numbers of up to n size to multiply, so overall it is O(n log n log log n log log log n)

Thus O(n^2) was more correct, in the same way that O(n!) was correct. Correct but unhelpful. And O(n) is simply wrong, without several assumptions that were not made.

Do note that you can do better with better multiplication algorithms.

Upvotes: 0

Turbofant
Turbofant

Reputation: 531

It's O(n), because, in the worst case, you perform x multiplications and tests, so your computation time grows linear with your input.

Upvotes: 1

Related Questions