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 :
>
> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
*RAHUL KUMAR DUBEY*
*BTech-3rd year *
*Computer Science &Engineering *
*Motilal Nehru National Institute Of Technology*
*Allahabad[211004],UP.*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
