Don, thanks for the solution, Can u pls explain how a+b gets reduced by atleast 25%
On Fri, Nov 16, 2012 at 3:42 AM, Don <[email protected]> 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 <[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. > > --
