GCD binary representation time complexity 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
Assuming x &lt;= 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 &lt;= I &lt;= sqrt (x) and x itself.