# 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