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.