If I have 2 Python lists:
a = [1, 2, 3, 4, 5]
b = [6, 7, 8, 9, 10]
and I say:
print(a + b)
I get
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
What is Python doing behind the scenes to create this result? What is the Big O runtime of the operations it performs?
p.s. If this has been asked before or is available elsewhere online I couldn't find it
according to this Link:
There are two ways to do concatenating: you can use the append method or the concatenation operator (+).
The append method is “amortized” O(1)O(1). In most cases, the memory required to append a new value has already been allocated, which is strictly O(1)O(1). Once the C array underlying the list has been exhausted, it must be expanded in order to accomodate further appends. This periodic expansion process is linear relative to the size of the new array, which seems to contradict our claim that appending is O(1)O(1).
However, the expansion rate is cleverly chosen to be three times the previous size of the array; when we spread the expansion cost over each additional append afforded by this extra space, the cost per append is O(1)O(1) on an amortized basis.
On the other hand, concatenation is O(k)O(k), where kk is the size of the concatenated list, since kk sequential assignment operations must occur.