The complexity is O(h^2) where h is the number of digits in the smaller
number *m* in base 10.
On Tue, Nov 13, 2012 at 3:34 PM, Shruti Gupta 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 :
>
> i
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
