#### Exercise 2.

We consider the following algorithm, which computes the gcd of two integer numbers.


==

1 		 		 if
then return

2 		 		 if

and

then return

3 		 		 if

and

then return

3 		 		 if

and

then return

4 		 		 if
then return

else  return



1. Let and the number of bits (in binary-expansion) of and respectively. Give an upper bound for the number of reursive calls needed to compute ?
2. Give an upper bound for the number of machine word operations needed for computing .