Big-O of list slicing Big-O of list slicing python python

Big-O of list slicing


python list big-o

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.

python list big-o

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

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

python list big-o

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.

Recent Posts
How can I color dots in a xy scatterplot according to column value?
How to update a claim in ASP.NET Identity?
What does {0} mean when initializing an object?
Accessing members of items in a JSONArray with Java
How to log SQL statements in Spring Boot?
Powershell Get-WebSite name parameter is ignored
How to detect scroll to bottom of html element
Java synchronized method
How to test controllers with CodeIgniter?
Detect Visual Composer
Matplotlib: Specify format of floats for tick labels
Rails join a list of strings with commas and "and" before the last