Well, if you want to be picky evaluating (calling) (xs ++ ys) takes whatever time it takes to evaluate xs to WHNF and if xs is null then it in addition takes the time it takes to evaluate ys to WHNF.&nbsp; Saying anything about time complexity with lazy evaluation requires a lot of context to be exact.<br>
<br>&nbsp; -- Lennart<br><br><div class="gmail_quote">On Mon, May 12, 2008 at 7:36 AM,  &lt;<a href="mailto:ajb@spamcop.net">ajb@spamcop.net</a>&gt; wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
G&#39;day all.<div class="Ih2E3d"><br>
<br>
Quoting Andrew Coppin &lt;<a href="mailto:andrewcoppin@btinternet.com" target="_blank">andrewcoppin@btinternet.com</a>&gt;:<br>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
The function (++) :: [x] -&gt; [x] -&gt; [x] has O(n) complexity.<br>
</blockquote>
<br></div>
That&#39;s not entirely true.<br>
<br>
When you call (++), it does O(1) work. &nbsp;If you evaluate k cons cells.<br>
it takes O(min(k,n)) work.<br>
<br>
Cheers,<br>
Andrew Bromage<div><div></div><div class="Wj3C7c"><br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br>