@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 [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.
