GCD(a, b) while b ̸= 0 do t ← b b ← a mod b a ← t end while
The
Algorithm Euclid(a,b)
Require: a, b ≥ 0
Ensure: a = GCD(a, b)
while b ̸= 0 do
t ← b
b ← a mod b
a ← t
end while
return a
We want to estimate its worst case running time using the big-Oh notation. Answer the following questions:
a. Let x be a integer stored on n bits. How many bits will you need to store x/2?
b. We note that if a ≥ b, then a mod b < a/2. Assume the values of the input integers a and b are encoded on n bits. How many bits will be used to store the values of a and b at the next iteration of the While loop?
c. Deduce from this observation, the maximal number iterations of the While loop the algorithm will do.
Step by step
Solved in 3 steps
