2 2. Let = 1+5 1.618 be a solution to 4 = 4+1. Show that...

Transcribed Image Text:

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: 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:

Answer rating: 100% (QA)

To show that the number of iterations made by Euclids algorithm on x y is at most logx y where 1618 ... View the full answer