On Mon, 2008-05-12 at 02:36 -0400, [EMAIL PROTECTED] wrote: > G'day all. > > Quoting Andrew Coppin <[EMAIL PROTECTED]>: > > > 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
