Re: [Haskell-cafe] List concat

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

G'day all.

Quoting Andrew Coppin :

...

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