What is the algorithmic complexity of retrieving a value by key from a Python dictionary?

The average-case algorithmic complexity of retrieving a value by key from a Python dictionary is O(1).

This is achieved through the use of hash tables. The key is hashed, and the resulting hash is used to determine the index (bucket) in the table where the corresponding value is stored. In an ideal case (without hash collisions), access to this bucket takes constant time.

In the worst case, with a large number of hash collisions, the complexity can reach O(n), where n is the number of elements in the dictionary. This occurs when all keys hash to the same bucket, and to find the desired value, all elements in that bucket must be sequentially checked. However, the standard implementation of dictionaries in Python uses collision resolution and rehashing mechanisms to minimize the likelihood of such scenarios.

# Retrieve value by key
value = my_dict[key]