## Slug #862

### append has bad complexity

**Description**

The `append`

function seems to have quite bad complexity.

N := 25000; L := []; t0 := CpuTime(); for i := 1 to N do append(ref L, i); endfor; println "Time to make list: ", TimeFrom(t0);

The above code takes about 1.2s on my computer; with `N`

doubled, it takes about 5.3s; and with `N`

multiplied by 4 it takes over 40s.

What is going on???

### History

#### #1 Updated by John Abbott about 2 years ago

The C++ STL offers an operation (`pushback`

) much like `append`

which guarantees linear complexity for a loop like the one I tried in CoCoA.

A naive implementation would have quadratic complexity: each call to `append`

makes a copy of the whole list.

How can CoCoA-5 have worse than quadratic complexity???

#### #2 Updated by John Abbott about 2 years ago

Just out of curiosity I ran the example with `N=20000`

; the time taken was about 210s... so still worse than quadratic behaviour, but not an increase by a factor of almost 8 as observed when increasing `N`

from 50000 to 100000.

Mysterious! Time to do some (painful) profiling... :-/