@Don : how can u say that a+b reduces by atleast 25% ..
in each iteration b won't be changed in (a+b). b just shifted to a. a gets
changed to a%b. ==> a+b will become at max 2b-1 .. we can't deduce any
relation between a+b to 2b-1.
why do we need the % of reduction on (a+b) in each iteration ?
On Fri, Nov 16, 2012 at 3:42 AM, Don <dondod...@gmail.com> wrote:
> 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 <fundooshr...@gmail.com> 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.
>
>
--
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.
