From: Mathieu Bouchard <matju@...>
Date: 2001-02-21T05:41:41+09:00
Subject: [ruby-talk:11186] Re: Generators (was: RCR Summary 02/16/01 -suspend)

> >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

Yes. Sorry.

matju