Please Solve this Q

Question

In the following C function, let n >= m.

int gcd(n,m)
{
  if (n%m ==0) return m;  
  n = n%m;
  return gcd(m,n);
}

How many recursive calls are made by this function? 

(A) (logn)?

(B) (n)

(C) (loglogn)

(D) (sqrt(n))

Answer 1

For gcd calculation.. The first condition of code is to check the best case which is of order O(1) the remaining code deals with worst case that is of order log(n)..  Therefore complexity will be of log(n).. For verification you can take value of m and n and then count the steps..