Re: List concat

by Derek Elkins :: Rate this Message:

On Mon, 2008-05-12 at 02:36 -0400, ajb@... wrote:

> G'day all.
>
> Quoting Andrew Coppin <andrewcoppin@...>:
>
> > The function (++) :: [x] -> [x] -> [x] has O(n) complexity.
>
> That's not entirely true.
>
> When you call (++), it does O(1) work. If you evaluate k cons cells.
> it takes O(min(k,n)) work.

I think we can safely simplify that to O(k) (at least for sequential
programs).

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

« Return to Thread: List concat

LightInTheBox - Buy quality products at wholesale price