@ 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 <fundooshr...@gmail.com>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 <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.
>>
>>
> --
>
>
>
--
