@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_and_da...@juno.com> 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 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.
>
--
