From: Elliot Temple <curi@...>
Date: 2006-07-14T07:59:43+09:00
Subject: Re: Recursion and Ruby


On Jul 13, 2006, at 3:48 PM, Robert Dober wrote:

> On 7/14/06, Douglas McNaught <doug@mcnaught.org> wrote:
>>
>> "Robert Dober" <robert.dober@gmail.com> writes:
>>
>> > On 7/13/06, Christian Neukirchen <chneukirchen@gmail.com> wrote:
>> >>
>> >> Given you have an reasonably exact approximation of the square  
>> root of
>> 5,
>> >> this can be done O(1)...
>> >
>> >
>> > I challange this, as there is no algorithm to compute c**n in O 
>> (1) it is
>> > O(log n).
>>
>> OT, but...
>>
>> http://mathforum.org/library/drmath/view/52686.html
>>
>> -Doug
>>
>> which means that you have to compute 2**n (2 is an approximation of
> sqrt(5)), right?
> which is O(?) ?

sqrt(5) can be pre-computed.

-- Elliot Temple
http://www.curi.us/blog/