$(8$ marks$)$ Recall that $GCD$ of two non$-$negative integers $m,n$ is the greatest positive

integer $p$ such that $p$ divides both $m$ and $n.$

Euclid gave the following algorithm for computing GCD $($where it is assumed that

$mn$ :

$GCD(m,n)$

If $m=0,$ then return $n.$

Else return $GCD(nmodm,m)$

END

Give as tight an upper bound as possible on the running time of the above algorithm

in terms of $n,$ the larger of the two inputs. You may assume that $"$ nmodm $"$ takes

constant time for this question.