1.  Consider the following algorithm for deciding GCD:

“On input :

1. If z doesn’t divide x or y, reject.               O(n)

2. For i from z + 1 to min(x,y) do:                  O(2^n)

    2.1. If i divides both x and y, reject.         O(n)

3. Accept.”                                           O(1)

Analyze the algorithm’s time complexity (in big-O notation).

n is the length of the max(x,y) So I was given an algorithm, the time complexity to the right is My addition and not part of this question. I want to make sure this is correct. I was thinking diving binary numbers is O(n) using long devision and step 2 just adds 0 or 1 to each previous number thus making the time exponential. Am I right ? Also, is there an algorithm that solves this in polynomial time ? Thanks


1 Answer 1


Assuming x <= y and no particularly clever division, it's O (x log x log x), if you don't divide y by I if x is already not divisible by I.

If z divides x and y then you just need to check if gcd (x/z, y/z) = 1. And only test 2 <= I <= sqrt (x) and x itself.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.