if (++) were left associative ?

[David Feuer]

On Sun, Apr 07, 2002, Konst Sushenko wrote:
> > 
> > I don't think so.  I think it only takes linear time to get the head.
> > But once you've gotten the head, it takes linear time again to get the
> > head of the tail, ....  You get (I think...) a progression like
> > n+(n-1)+(n-2)+...+1, which is in O(n^2).
> > 
> 
> What does 'n' denote?
> 
> The get the head, it takes time proportional to the number of (++)
> invocations. Is that what you mean?

Yes.  Things depend somewhat on how the lengths of the lists being
concatenated relate to the number of lists being concatenated, but I
don't want to think about that now.

David