# How many recursive calls are made by this gcd function?

In the following 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?

• $\Theta (\log_2 n)$
• $\Omega (n)$
• $\Theta (\log_2(\log_2 n))$
• $\Theta ( \sqrt{n} )$

I think the answer is $\Theta (\log_2(\log_2n))$, but my book is saying $\Theta (\log_2 n)$.

My reasoning is as follows. Here we are not dividing the number. If there was a division then it would be $\log n$. But here operation is $\bmod$. So we will get a very small number after the first call. So it must be $\log \log n$. Am I thinking correctly?

• Hint: try to run it on two consecutive Fibonacci numbers. See what happens. – Shaull Aug 15 '13 at 17:33
• – Dan D. Aug 15 '13 at 19:19

Hint: on input $F_{n+1},F_n$, gcd makes a recursive call with inputs $F_n,F_{n-1}$. Now use the asymptotic formula $F_n = \phi^n + \Theta(1)$, where $\phi = (1+\sqrt{5})/2 > 1$.

Also, while we're at it, $\Theta(\log_2 n) = \Theta(\log n)$, and similarly $O(\log_2 n) = O(\log n)$ (and the same fore $\log\log n$); try to figure out why (here the base of $\log n$ can be arbitrary, but for definiteness you can choose base $e$).

• +1 I think you meant to write that "... gcd makes a recursive call that produces outputs $F_n, F_{n-1}$. – Dilip Sarwate Aug 17 '13 at 23:40
• gcd only outputs one value. – Yuval Filmus Aug 18 '13 at 0:03
• I meant to say that the gcd routine with inputs $(F_{n+1}, F_n)$ executes a division (which ends up being just one subtraction that produces $F_{n-1}$ in the Fibonacci case) and then calls gcd (recursively) with inputs $(F_n, F_{n-1})$ and this process continues until the division step executes with no remainder. – Dilip Sarwate Aug 18 '13 at 0:13

First thing, drop the $2$ !! Here's the reason.. asymptotics don't really care much for the constants in the bases... $$log_an = \frac{log_bn}{log_ba}$$ Now $log_ba$ is a just another constant, so you can drop it..

Now, about your question, the most important thing to notice here is the recursion...

• If you stare at the algorithm for sometime, you will see that the remainder is 'cut' into half in every 2 steps.
• And since it cannot go less than 1, there can be atmost $2.[log_2 n]$ steps/recursions.
• Each step/recursion requires constant time, $\theta(1)$
• so this can be atmost $2.[log_2 n].\theta(1)$ time
• and that's $\theta(log$ $n)$

that was fun, right? :)

now, 'see' that our proof is fundamentally based on the observation that the remainder halves in every two steps make sure you prove that, (hint: i did my proofs with 'proof by cases method' and 'contradiction method')