[Haskell-cafe] List concat
derek.a.elkins at gmail.com
Mon May 12 12:25:10 EDT 2008
On Mon, 2008-05-12 at 02:36 -0400, ajb at spamcop.net wrote:
> G'day all.
> Quoting Andrew Coppin <andrewcoppin at btinternet.com>:
> > 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
More information about the Haskell-Cafe