Tail recursion is no different than a loop, so the complexity is the
same as an iterative solution like this:
int gcd(int a, int b) // For a<b
{
while(1)
{
int c = a % b;
if (!c) return b;
a = b;
b = c;
}
}
The complexity is log(a) + log(b) because each iteration reduces a+b
by at least 25%.
Don
On Nov 13, 5:04 am, Shruti Gupta <[email protected]> wrote:
> hi
>
> Can anyone help me find out the time complexity of recursive gcd algorithm
> (using euclid's algo)
> i.e. for the following program :
>
> int gcd(int n,int m) //given n>m
> {
> if(n%m==0)
> return m;
> else
> return gcd(m,n%m);
>
> }
>
> i think the soln is lg(a*b) but have no idea how..
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
