python array time complexity?

Question

What's the .append time complexity of array.array and np.array ?

I see time complexity for list, collections.deque, set, and dict in python_wiki , but I can't find the time complexity of array.array and np.array. Where can I find them?

Answer 1

So to link you provided (also a TLDR) list are internally "represented as an array" _link It's supposed to be O(1) with a note at the bottom saying:

"These operations rely on the "Amortized" part of "Amortized Worst Case". Individual actions may take surprisingly long, depending on the history of the container." _link

---

More details

It doesn't go into detail in the docs but if you look at the source code you'll actually see what's going on. Python arrays have internal buffer(s) that allow for quick resizing of themselves and will realloc as it grows/shrinks.

array.append uses arraymodule.array_array_append which calls arraymodule.ins calling arraymodule.ins1 which is the meat and potatoes of the operation. Incidentally array.extend uses this as well but it just supplies it Py_SIZE(self) as the insertion index.

So if we read the notes in arraymodule.ins1 it starts off with:

Bypass realloc() when a previous overallocation is large enough
to accommodate the newsize.  If the newsize is 16 smaller than the
current size, then proceed with the realloc() to shrink the array.

^link

...

This over-allocates proportional to the array size, making room
for additional growth.  The over-allocation is mild, but is
enough to give linear-time amortized behavior over a long
sequence of appends() in the presence of a poorly-performing
system realloc().
The growth pattern is:  0, 4, 8, 16, 25, 34, 46, 56, 67, 79, ...
Note, the pattern starts out the same as for lists but then
grows at a smaller rate so that larger arrays only overallocate
by about 1/16th -- this is done because arrays are presumed to be more
memory critical.

^link