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,

Vicegerent

Answer 1

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.

Snoopy

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? – Anticipation

Update: I wrote a custom iterable class that iterates over my existing list, it should have no penalties. – Anticipation

Answer 2

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

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

Xiomaraxiong

Answer 3

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.

Krimmer

Answer 4

Its just the difference between the largest value in the slice and the lowest value in slice, you could think of it like: O(LARGEST_NUM - LOWEST_NUM) cause python only iterates from lowest to largest but you wanna get a positive number since it cant be negative. Or you could just say O( |LOWEST_NUM - LARGEST_NUM| ) where | | is the absolute value. In competitive programming, if a problem involves list slicing, there is almost always a test case where the difference is roughly O(N) so if you do CP just watch out for that.

Qadi

This answer implies that the values inside the list matter to the speed of slicing, which isn't true. I'd suggest editing it to make that clear. – Soonsooner