0

I have the following C code. I wanted to know how many recursive calls are made by this function?

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

The answer is O(log n) . In my view, it should be O(n) . Please explain how it is O(log n).

Thanks in advance.

Gaurang Tandon
  • 6,504
  • 11
  • 47
  • 84
  • 3
    Why do you think it should be O(n)? Have you tried writing out all calls for a few cases of the function call (to get more intuition into how it works)? – Bernhard Barker Nov 15 '13 at 13:32
  • @Dukeling Ok, sorry, I did not try that out, will do. I have edited the question. – Gaurang Tandon Nov 15 '13 at 13:35
  • Please note the number of calls in `gcd` are `log(n)` **on average**. There are some cases when the function makes no recursive calls (for instance if `m` divides `n`). – Ivaylo Strandjev Nov 15 '13 at 13:37
  • The number of call is not equivalent to n, it is equivalent to log(n). It means that if gcd(n,m) does X calls, gcd(n^2,m) will do 2X calls (roughly, but complexity is something you should look into). – Fabinout Nov 15 '13 at 13:38
  • @IvayloStrandjev and @Fabinout Thanks for that. I understand the point you make. However, I am actually having difficulty in computing the answer you see. I don't know how to do that. For example, if I get an algorithm like this - `int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor(sqrt(n))) + n); }` Then , How will I compute the number of recursive calls. Like, there must be standard of procedures or something like that ... – Gaurang Tandon Nov 15 '13 at 13:42
  • see http://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm – Leeor Nov 15 '13 at 13:49
  • Yes, there will be at most (5 times the number of digits) calls. It means that if you calculate a number which is a power of the previous one, you'll only have a few more calls to do. – Fabinout Nov 15 '13 at 13:53

0 Answers0