Python Set Slice Complexity

Question

Assume that I have two lists named a and b of both size n, and I want to do the following slice setting operation with k < n

a[:k] = b[:k]

In the Python wiki's Time Complexity page it says that the complexity of slice setting is O(n+k) where k is the length of the slice. I just cannot understand why it is not just O(k) in the above situation.

I know that slicing returns a new list, so it is O(k), and I know that the list holds its data in a continuous way, so inserting an item in the middle would take O(n) time. But the above operation can easily be done in O(k) time. Am I missing something?

Furthermore, is there a documentation where I can find detailed information about such issues? Should I look into the CPython implementation?

Thanks.

Since the n elements that the container contains are indexed once, isn't it? I am no expert but it makes plain sense to me like this. — Abhinav
– Abhinav, Commented Dec 18, 2015 at 13:32

Martijn Pieters · Accepted Answer · 2015-12-18 13:48:43Z

11

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

Your case, where you replace the slice with an equal number of new elements, the implementation only takes O(k) steps. But given all possible combinations of number of elements inserted and deleted, the average case has to move the n remaining elements in the list up or down.

See the list_ass_slice function for the exact implementation.

answered Dec 18, 2015 at 13:48

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Wander Nauta · Accepted Answer · 2015-12-18 13:49:50Z

3

You're right, if you want to know the exact details it's best to use the source. The CPython implementation of setting a slice is in listobject.c.

If I read it correctly, it will...

Count how many new elements you're inserting (or deleting!)
Shift the n existing elements of the list over enough places to make room for the new elements, taking O(n) time in the worst case (when every element of the list has to be shifted).
Copy over the new elements into the space that was just created, taking O(k) time.

That adds up to O(n+k).

Of course, your case is probably not that worst case: you're changing the last k elements of the list, so there might be no need for shifting at all, reducing the complexity to O(k) you expected. However, that is not true in general.

edited Dec 18, 2015 at 13:49

answered Dec 18, 2015 at 13:41

Wander Nauta

19.7k1 gold badge50 silver badges65 bronze badges

Collectives™ on Stack Overflow

Python Set Slice Complexity

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related