How to determine the time complexity of an operation for searching an element in a list?

The time complexity of searching for an element in a list depends on the type of list and the search method:

• If it is a regular Python list, then searching for an element by value is a linear search operation, since the list is neither sorted nor indexed by value. In the worst case, all elements need to be checked, so the complexity is O(n), where n is the length of the list.

• If the list is sorted, binary search can be used, which operates in O(log n), but this requires either using special data structures or implementing binary search manually.

• If a faster check for the presence of an element is needed, it is better to use sets or dictionaries, where key lookup is performed in amortized O(1).

Example of linear search:

my_list = [3, 5, 7, 9]
value = 7
found = value in my_list  # O(n)

For binary search, the bisect module can be used if the list is sorted:

import bisect
my_list = [1, 3, 5, 7, 9]
value = 7
index = bisect.bisect_left(my_list, value)
found = index < len(my_list) and my_list[index] == value  # O(log n)