Complexity of list.index(x) in Python

python algorithm list big-o performance
user734027 picture user734027 · May 6, 2011 · Viewed 44k times · Source

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?

Answer

zeekay picture zeekay · May 6, 2011

It's O(n), also check out: http://wiki.python.org/moin/TimeComplexity

This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have slightly different performance characteristics. However, it is generally safe to assume that they are not slower by more than a factor of O(log n)...

Related questions

Removing duplicates in the lists

Pretty much I need to write a program that checks if a list has any duplicates and if it does it removes them and returns a new list with the items that weren't duplicated/removed. This is what I have …

Read More
Permutations between two lists

I’m having trouble wrapping my head around a algorithm I’m try to implement. I have two lists and want to take particular combinations from the two lists. Here’s an example. names = 'a', 'b' numbers = 1, 2 the output in …

Read More
Pythonic way to check if a list is sorted or not

Is there a pythonic way to check if a list is already sorted in ASC or DESC listtimestamps = [1, 2, 3, 5, 6, 7] something like isttimestamps.isSorted() that returns True or False. I want to input a list of timestamps for some messages and check …

Read More