Python Set Slice Complexity

Question

Suppose I have two lists with names a and b of both sizes n, and I want to perform the following operation to set a slice with k <n

a[:k] = b[:k] 

The Python wiki Time Complexity page says that the complexity of setting the slice is O (n + k), where k is the length of the slice. I just can't understand why this is not just O (k) in the above situation.

I know that slicing returns a new list, so this is O (k), and I know that the list stores its data in continuous mode, so inserting an element in the middle will take O (n) time. But the above operation can be easily performed in O (k) time. Did I miss something?

Also, is there any documentation where I can find detailed information about such issues? Should I take a look at CPython implementation?

Thanks.

Answer 1

O (n + k) is the average case, which includes the need to grow or shrink the list to adjust the number of inserted elements to replace the original slice.

In the case when you replace the slice with an equal number of new elements, the implementation performs only O (k) steps. But, taking into account all possible combinations of the number of inserted and deleted elements, the average case should move the n remaining elements in the list up or down.

For an exact implementation, see the list_ass_slice function.

Answer 2

You are right if you want to know which details are better to use the source. CPython implementation of slice setup in listobject.c .

If I read it correctly, it will ...

• Indicate the number of new items that you insert (or delete!)
• Shift n existing list items by enough space to make room for new items, taking O (n) time in the worst case (when each list item needs to be shifted).
• Copy the new elements into the space you just created using O (k) time.

This adds up to O (n + k).

Of course, your case is probably not in the worst case: you change the last elements of k in the list, so you don’t need to translate at all, reducing the complexity to O (k) that you expected. However, this is not so at all.

Answer 3

I can answer the second part of your question, using Numpy is much easier instead, and in my experience I don't see speed improvements using CPython for indexing, since Numpy has been highly optimized for vectorization and indexing.