Big-O of list slicing

Question

Say I have some Python list, my_list which contains N elements. Single elements may be indexed by using my_list[i_1], where i_1 is the index of the desired element. However, Python lists may also be indexed my_list[i_1:i_2] where a "slice" of the list from i_1 to i_2 is desired. What is the Big-O (worst-case) notation to slice a list of size N?

Personally, if I were coding the "slicer" I would iterate from i_1 to i_2, generate a new list and return it, implying O(N), is this how Python does it?

Thank you,

score 55 · Accepted Answer · edited Jun 01 '20 at 19:09

55

Getting a slice is O(i_2 - i_1). This is because Python's internal representation of a list is an array, so you can start at i_1 and iterate to i_2.

For more information, see the Python Time Complexity wiki entry

You can also look at the implementation in the CPython source if you want to.

edited Jun 01 '20 at 19:09

Boris Verkhovskiy

10,733
7
77
79

answered Nov 02 '12 at 22:01

Sam Mussmann

5,653
2
28
43

I just need my_list[1:] but performed often, so it looks like it will double to complexity vs my_list. My lists have fixed size, the elements may change values. How expensive is to keep a reference to slice of a fixed list? – uuu777 Nov 22 '20 at 14:04
Update: I wrote a custom iterable class that iterates over my existing list, it should have no penalties. – uuu777 Nov 22 '20 at 15:57

score 31 · Answer 2 · answered Nov 02 '12 at 22:01

31

according to http://wiki.python.org/moin/TimeComplexity

it is O(k) where k is the slice size

answered Nov 02 '12 at 22:01

Joran Beasley

103,130
11
146
174

score 10 · Answer 3 · answered Nov 02 '12 at 22:01

For a list of size N, and a slice of size M, the iteration is actually only O(M), not O(N). Since M is often << N, this makes a big difference.

In fact, if you think about your explanation, you can see why. You're only iterating from i_1 to i_2, not from 0 to i_1, then I_1 to i_2.

Big-O of list slicing

3 Answers3

Linked

Related