Big-O of list slicing

python list big-o
mjgpy3 picture mjgpy3 · Nov 2, 2012 · Viewed 26.5k times · Source

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,

Answer

Sam Mussmann picture Sam Mussmann · Nov 2, 2012

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.

Related questions

Complexity of list.index(x) in Python

I'm referring to this: http://docs.python.org/tutorial/datastructures.html What would be the running time of list.index(x) function in terms of big O notation?

Read More
Finding the index of an item in a list

Given a list ["foo", "bar", "baz"] and an item in the list "bar", how do I get its index (1) in Python?

Read More
How do I get the number of elements in a list?

Consider the following: items = [] items.append("apple") items.append("orange") items.append("banana") # FAKE METHOD: items.amount() # Should return 3 How do I get the number of elements in the list items?

Read More