What is the complexity of basic operations with…

The complexity of basic operations with collections in Python (list, dictionary, set) can be represented in a table:

Operation	List (`list`)	Dictionary (`dict`)	Set (`set`)
Element search	O(n)	O(1)	O(1)
Element insertion	O(1)	O(1)	O(1)
Element deletion	O(1)	O(1)	O(1)
Access by index	O(1)	N/A	N/A
Iteration	O(n)	O(n)	O(n)
Collection length	O(1)	O(1)	O(1)

Explanations:

O(1) - Constant complexity: The operation is performed in fixed time, regardless of the collection size.
O(n) - Linear complexity: The execution time is proportional to the size of the collection.
Search, insertion, and deletion in lists require shifting elements, which takes time depending on the position of the element and the list size.
Dictionaries and sets use hash tables, which provide average constant time for search, insertion, and deletion. Collisions can degrade these operations to O(n), but this is rare in practice.
Access by index in lists is O(1), as elements are stored sequentially in memory.
Iteration over all collection elements always takes time proportional to their number (O(n)).
Getting the length of a collection (len()) is O(1) for all these types, as the length is stored separately.

Example of searching for an element in a list:

# Searching for an element in a list requires traversal
my_list = [1, 2, 3, 4, 5]
if 3 in my_list:
    pass # O(n) in the worst case

Example of searching for an element in a dictionary:

# Searching for an element in a dictionary - O(1) on average
my_dict = {'a': 1, 'b': 2, 'c': 3}
if 'b' in my_dict:
    pass # O(1) on average

Example of adding an element to the end of a list:

# Adding an element to the end of a list - O(1) on average (amortized)
my_list = [1, 2, 3]
my_list.append(4) # O(1) on average

Example of adding an element to the beginning of a list:

# Adding an element to the beginning of a list - O(n)
my_list = [1, 2, 3]
my_list.insert(0, 0) # O(n)

What is the complexity of basic operations with collections in Python?