I think I would like to make another note: when we talk about the complexity of a function, we are talking about the time taken to completely evaluate the result. Otherwise any expression in haskell will be O(1), since it just creates a thunk.<br>
And then the user of the program is to be blamed for running the program, since that is what caused evaluation of those thunks :)<br><br><br>Abhay<br><br><div class="gmail_quote">2008/5/31 Martin Geisler &lt;<a href="mailto:mg@daimi.au.dk">mg@daimi.au.dk</a>&gt;:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Tillmann Rendel &lt;<a href="mailto:rendel@daimi.au.dk">rendel@daimi.au.dk</a>&gt; writes:<br>

<br>
Hi! (Cool, another guy from DAIMI on haskell-cafe!)<br>
<div class="Ih2E3d"><br>
&gt; Another (n - 1) reduction steps for the second ++ to go away.<br>
&gt;<br>
&gt; &nbsp; &nbsp; &nbsp; &nbsp; last (&quot;o&quot; ++ &quot;l&quot;)<br>
&gt; A) &nbsp;~&gt; &nbsp;last (&#39;o&#39; : &quot;&quot; ++ &quot;l&quot;))<br>
&gt; L) &nbsp;~&gt; &nbsp;last (&quot;&quot; ++ &quot;l&quot;)<br>
&gt; A) &nbsp;~&gt; &nbsp;last (&quot;l&quot;)<br>
&gt; L) &nbsp;~&gt; &nbsp;&#39;l&#39;<br>
&gt;<br>
&gt; And the third and fourth ++ go away with (n - 2) and (n - 3) reduction<br>
&gt; steps. Counting together, we had to use<br>
&gt;<br>
&gt; &nbsp; n + (n - 1) + (n - 2) + ... = n!<br>
&gt;<br>
&gt; reduction steps to get rid of the n calls to ++, which lies in O(n^2).<br>
&gt; Thats what we expected of course, since we know that each of the ++<br>
&gt; would need O(n) steps.<br>
<br>
</div>I really liked the excellent and very clear analysis! But the last<br>
formula should be:<br>
<br>
 &nbsp; n + (n - 1) + (n - 2) + ... = n * (n+1) / 2<br>
<br>
which is still of order n^2.<br>
<font color="#888888"><br>
--<br>
Martin Geisler<br>
<br>
VIFF (Virtual Ideal Functionality Framework) brings easy and efficient<br>
SMPC (Secure Multi-Party Computation) to Python. See: <a href="http://viff.dk/" target="_blank">http://viff.dk/</a>.<br>
</font><br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">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>
<br></blockquote></div><br>