@Pralaybi: You've got it right. Since h is proportional to the log of the
smaller number, we also can say that the complexity is O(log^2 (smaller
number)).
Dave
On Friday, November 23, 2012 2:09:01 PM UTC-6, pralaybi...@gmail.com wrote:
> @Dave: Could you please correct me if am wrong here.
> 1) So we are looking out for the worst case, and that happens when m and n
> are consecutive Fibo numbers, being mutually prime to reach other.
> 2) Its taking 5 iterations to reduce the number of digits in the smaller
> of m and n, by one. Assuming there are "h" digits in the smaller number
> from now on.
> 3) Also, the computation cost is proportional to the number of digits,
> hence cost is proportional to h. (Could you please elaborate a lil more on
> this)
> 4) So net complexity is h*h = O(quadratic)
>
> On Fri, Nov 16, 2012 at 8:50 PM, Dave <dave_an...@juno.com
> <javascript:>>wrote:
>
>> @Sonesh: Not so. The worst case for Euclid's algorithm is when the
>> numbers are consecutive Fibonacci numbers. So (89,55) --> (55,34) -->
>> (34,21) --> (21,13) --> (13,8) --> (8,5), so it took 5 steps to reduce the
>> number of digits of the first number from 2 to 1. Asymptotically, the
>> number of digits reduces by log_10(phi) = log_10((1+sqrt(5))/2) ~= 0.209,
>> where phi is the Golden Ratio, so it takes, on average, ~4.78 iterations to
>> reduce the numbers by 1 digit, in the worst case. But still, we can say
>> that Euclid's algorithm is O(log n).
>>
>> Dave
>>
>> On Friday, November 16, 2012 6:40:58 PM UTC-6, sonesh wrote:
>>
>>> you see, in each step of recursion, the number of digits in *n* is
>>> decrease by one(at least in worst case), so the complexity you can decide.
>>>
>>> On Tuesday, November 13, 2012 3:34:06 PM UTC+5:30, Shruti 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 view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/bCB-L41X6ukJ.
>>
>> 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.
>>
>
>
--
