@ Dave : can u pls explain the solution u gave . How can u say fibnocci sequence produces worst case ?
On Fri, Nov 16, 2012 at 11:15 AM, Shruti Gupta <[email protected]>wrote: > 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. >> >> > -- > > > --
