2. The greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. When GCD is equal to 1, the two numbers are called relatively prime or coprime. We can use the following efficient algorithm to find GCD between two integers.

GCD (m,n)

if m mod n == 0

return n

return GCD (n, m mod n)

Overview of GCD (m, n)

- Divide m by n and get the remainder r. If r == 0, return n as the GCD of m and n.

- Replace m by n and replace n by r. Return to step 1.

(a) What is the recurrence of GCD algorithm?

T(n) =

(b) Solve the above recurrence and find the running time of GCD algorithm.