Search code examples
pythonlistbig-o

Big-O of list slicing

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,

Solution

  • 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.