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: 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$).

  • $\begingroup$ +1 I think you meant to write that "... gcd makes a recursive call that produces outputs $F_n, F_{n-1}$. $\endgroup$ – Dilip Sarwate Aug 17 '13 at 23:40
  • $\begingroup$ gcd only outputs one value. $\endgroup$ – Yuval Filmus Aug 18 '13 at 0:03
  • $\begingroup$ 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. $\endgroup$ – 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')


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.