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