Euclid's Algorithm for Computing GCD:

Given a and b such that a $>=$ b:

$1.$ Analyse Algorithm $1$ to identify its best and worst$-$case complexity.

$[1$ point$]$

$2.$ Provide tight asymptotic bounds for the algorithm. Justify your

answer. $[1$ point$]$

Hint: You may use the binary representations of a and b and the worst

and the best case scenarios in terms of the number of computations in all iterations.