In the following C function, let n >= m. int gcd(n,m) { if (n%m ==0) return m;…

PYQ GATE 2007

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?

  1. A.

    Θ(logn)

  2. B.

    Ω(n)

  3. C.

    Θ(loglogn)

  4. D.

    Θ(sqrt(n))

Attempted by 109 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…