[Haskell-cafe] Question about memory usage

Sebastian Fischer sebf at informatik.uni-kiel.de
Tue Aug 17 03:02:58 EDT 2010


On Aug 17, 2010, at 8:39 AM, Roel van Dijk wrote:

> That is an interesting trick. So there exists an algorithm that
> calculates Fibonacci numbers in O(log n) time.

This is what my program does. But it's only O(long n) if you assume  
multiplication is constant time (which it is not for large numbers).

Sebastian


-- 
Underestimating the novelty of the future is a time-honored tradition.
(D.G.)





More information about the Haskell-Cafe mailing list