Am Sa., 5. Sept. 2020 um 14:58 Uhr schrieb Marc Nieper-Wißkirchen
<xxxxxx@nieper-wisskirchen.de>:

> Please take into consideration that, as Wolfgang observed, vectors
> have no O(1) random access guarantee. There are meaningful
> implementions of vectors conceivable that have, say, O(log n) random
> access time.

Actually, such implementations are not only conceivable but, given the
illusion of unlimited space, the standard implementation of a vector
has O(log n) random access time:

(vector-ref vec i) => [fetch value at location vector-base(vec) + i]

So, complexity comes from the addition, which is O(log n) in the size
n of the added numbers.

That it does not matter in practice, is due to the fact that n is
usually bounded by the size of the computer's memory. When we talk
about algorithmic complexities, though, it only makes sense if we view
the independent variable (n in this example) as potentially
arbitrarily large. (Otherwise, merge sort would sort in O(n) or even
in O(1)...)