2 2. Let = 1+5 1.618 be a solution to 4 = 4+1. Show that the number of iterations (not including the base case) made by Euclid's algorithm on (x, y) is at most log (x + y). Note that this is a slight improvement over the bound of log3/2(x + y) that was shown in class. Hint: Change the potential function from class to s(x, y) = cxy for a suitable constant c. Try using c = 4. Consider the crucial point that +1 = 4 and/or other similar relations satisfied by 4. Solution: