Sorry, I said that wrong. a+b is reduced by 25% over any TWO
iterations.
Look at these cases
2a <= b : b % (a % b) < a and 2*a <= b, so b is decreased by at least
half, so a+b decreased by at least 25%
a < b : b will become b-a, which is less than b/2, decreasing a+b
by at least 25%.
a==b : a+b becomes zero
Don
On Nov 16, 9:23 am, bharat b <bagana.bharatku...@gmail.com> wrote:
> @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.
