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

O(1) on average (for a hashed table). In the worst case, with collisions, it can be O(N), but this is a very rare occurrence with a good hash function.