Q44

MCQ2 marks, −0.5

In the following C function, let $n \geq 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)

$\Theta(\log_2n)$

(B)

$\Omega(n)$

(C)

$\Theta(\log_2\log_2n)$

(D)

$\Theta(\sqrt{n})$

Loading…