# if (++) were left associative ?

**David Feuer
**
dfeuer@cs.brown.edu

*Sun, 7 Apr 2002 18:06:27 -0400*

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