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?

Answers:

Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.

Method 1

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)…

Method 2

According to said documentation:

list.index(x)

Return the index in the list of the first item whose value is x.
It is an error if there is no such item.

Which implies searching. You’re effectively doing x in s but rather than returning True or False you’re returning the index of x. As such, I’d go with the listed time complexity of O(n).

Method 3

Any list implementation is going to have an O(n) complexity for a linear search (e.g., list.index). Although maybe there are some wacky implementations out there that do worse…

You can improve lookup complexity by using different data structures, such as ordered lists or sets. These are usually implemented with binary trees. However, these data structures put constraints on the elements they contain. In the case of a binary tree, the elements need to be orderable, but the lookup cost goes down to O(log n).

As mentioned previously, look here for run time costs of standard Python data structures:
http://wiki.python.org/moin/TimeComplexity

Method 4

Use the following code to check the timing. Its complexity is O(n).

import time


class TimeChecker:

    def __init__(self, name):
        self.name = name

    def __enter__(self):
        self.start = self.get_time_in_sec()
        return self

    def __exit__(self, exc_type, exc_val, exc_tb):
        now = self.get_time_in_sec()
        time_taken = now - self.start  # in seconds
        print("Time Taken by " + self.name + ": " + str(time_taken))

    def get_time_in_sec(self):
        return int(round(time.time() * 1000))


def test_list_index_func(range_num):
    lis = [1,2,3,4,5]
    with TimeChecker('Process 1') as tim:
        for i in range(range_num):
            lis.index(4)

test_list_index_func(1000)
test_list_index_func(10000)
test_list_index_func(100000)
test_list_index_func(1000000)

print("Time: O(n)")

Method 5

The documentation provided above did not cover list.index()

from my understanding, list.index is O(1) operation.
Here is a link if you want to know more. https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

Method 6

Try this code, it will help you to get your execution time taken by lis.index operator.

import timeit
lis=[11,22,33,44,55,66,77] 
for i in lis: 
    t = timeit.Timer("lis.index(11)", "from main import lis") 
    TimeTaken= t.timeit(number=100000) 
    print (TimeTaken)

All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0