Does this sentence contradicts the python paradigm “list should not be initialized”?

People coming from other coding languages to python often ask how they should pre-allocate or initialize their list. This is especially true for people coming from Matlab where codes as

l = []
for i = 1:100
    l(end+1) = 1;
end

returns a warning that explicitly suggest you to initialize the list.

There are several posts on SO explaining (and showing through tests) that list initialization isn’t required in python. A good example with a fair bit of discussion is this one (but the list could be very long): Create a list with initial capacity in Python

The other day, however, while looking for operations complexity in python, I stumbled this sentence on the official python wiki:

the largest [cost for list operations] come from growing beyond the current allocation size (because everything must move),

This seems to suggest that indeed lists do have a pre-allocation size and that growing beyond that size cause the whole list to move.

This shacked a bit my foundations. Can list pre-allocation reduce the overall complexity (in terms of number of operations) of a code? If not, what does that sentence means?

EDIT:

Clearly my question regards the (very common) code:

container = ... #some iterable with 1 gazilion elements
new_list = []
for x in container:
    ... #do whatever you want with x
    new_list.append(x) #or something computed using x
    

In this case the compiler cannot know how many items there are in container, so new_list could potentially require his allocated memory to change an incredible number of times if what is said in that sentence is true.

I know that this is different for list-comprehensions

Answer

Can list pre-allocation reduce the overall complexity (in terms of number of operations) of a code?

No, the overall time complexity of the code will be the same, because the time cost of reallocating the list is O(1) when amortised over all of the operations which increase the size of the list.

If not, what does that sentence means?

In principle, pre-allocating the list could reduce the running time by some constant factor, by avoiding multiple re-allocations. This doesn’t mean the complexity is lower, but it may mean the code is faster in practice. If in doubt, benchmark or profile the relevant part of your code to compare the two options; in most circumstances it won’t matter, and when it does, there are likely to be better alternatives anyway (e.g. NumPy arrays) for achieving the same goal.

new_list could potentially require his allocated memory to change an incredible number of times

List reallocation follows a geometric progression, so if the final length of the list is n then the list is reallocated only O(log n) times along the way; not an “incredible number of times”. The way the maths works out, the average number of times each element gets copied to a new underlying array is a constant regardless of how large the list gets, hence the O(1) amortised cost of appending to the list.