From: Robert Dober <robert.dober@...>
Date: 2006-07-14T08:03:51+09:00
Subject: Re: Recursion and Ruby

------=_Part_15817_17886951.1152831828951
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

On 7/14/06, Elliot Temple <curi@curi.us> wrote:
>
>
> 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.


obviously my didactic powers are limited :(

In order to compute f(n), you need to compute sqrt(5)**n, which is O(log
n).

Cheers
Robert

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


--=20
Deux choses sont infinies : l'univers et la b=EAtise humaine ; en ce qui
concerne l'univers, je n'en ai pas acquis la certitude absolue.

- Albert Einstein

------=_Part_15817_17886951.1152831828951--