[nem-en] Lists and indexes

[Michal Moskal]

On 2/21/07, Vladimir Reshetnikov <v.reshetnikov at gmail.com> wrote:
> It is generally known, that string concatenation in a loop has the
> quadratic complexity.

Yeah -- because several people has been bitten by it and C#/Java
programmers generally know that. So we don't consider it much of a
problem for a list too.

OTOH, depending on how you concatenate, it might be possible to get
linear complexity for lists, because each operation is linear only in
size of the first parameter and constant in size of the second, so res
= x + res is O(n), but res = res + x is O(n^2).

However, it wouldn't be generally known that list indexing is not
constant time...

-- 
   Michał