@Bharat: See, e.g.,
http://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency.
Dave
On Sunday, November 18, 2012 12:03:33 AM UTC-6, bharat wrote:
> @ 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
> <fundoo...@gmail.com<javascript:>
> > 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 <dond...@gmail.com <javascript:>>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 algo...@googlegroups.com<javascript:>
>>> .
>>> To unsubscribe from this group, send email to
>>> algogeeks+...@googlegroups.com <javascript:>.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>> --
>>
>>
>>
>
>
--
