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? konst
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
participants (2)
-
David Feuer -
Konst Sushenko