72

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,

0

3 Answers 3

65

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.

2
  • 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, 2020 at 14:04
  • Update: I wrote a custom iterable class that iterates over my existing list, it should have no penalties.
    – uuu777
    Nov 22, 2020 at 15:57
40

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

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

10

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.