Menu
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,
397
it is O(k) where k is the slice size.
Short answer: str slices, in general, copy. That means that your function that does a slice for each of your string's n suffixes is doing O(n2) work.
Constructing a slice that is a fraction of n takes O(n) time. In this related post the python notation is explained. You may also take a look at the python documentation on the time complexities. So the answer is no in general, only for a constant size slice it can be constant time.
If some slicing expressions are made that do not make sense or are incomputable then empty lists are generated. List[2:4] = ['Geeks', 'for', 'Geeks', '!'] List slicing can be used to modify lists or even delete elements from a list. By concatenating sliced lists, a new list can be created or even a pre-existing list can be modified.
In Python, list slicing is a common practice and it is the most used technique for programmers to solve efficient problems. Consider a python list, In-order to access a range of elements in a list, you need to slice a list. One way to do this is to use the simple slicing operator i.e. colon (:)
One way to do this is to use the simple slicing operator : With this operator you can specify where to start the slicing, where to end and specify the step. If L is a list, the expression L [ start : stop : step ] returns the portion of the list from index start to index stop, at a step size step. Here is a basic example of list slicing.
You can also specify negative indices while slicing a list. You can specify both positive and negative indices at the same time. You can specify the step of the slicing using step parameter. The step parameter is optional and by default 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.
158
according to http://wiki.python.org/moin/TimeComplexity
it is O(k) where k is the slice size
30
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
