From: Ben Tilly <ben_tilly@...>
Date: 2001-02-21T03:03:39+09:00
Subject: [ruby-talk:11183] Re: Generators (was: RCR Summary 02/16/01 -suspend)

Mathieu Bouchard <matju@cam.org> wrote:
>
>On Mon, 19 Feb 2001, Christoph Rippel wrote:
>
[...]
>Despite a regular functional implementation of fib(n) being in O(fib(n))
>time (that is, O(1.618**n) time), the implementation with generators is in
>O(n) time like yours [*]...
[...]
>[*] actually that's for small numbers. For large ones, it's O(n log n).
>The other one is similarly slower but it doesn't matter because no-one
>can run that on big numbers.

Actually isn't it O(n*n)?  There are n steps, with numbers
that increase exponentially in size, whose representations
therefore grow linearly, making the amount of work to do any
addition linear in how many steps have been taken.  So you
have n steps of work O(n), for O(n*n) total.

(Which is still much better than exponential work!)

Cheers,
Ben
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com