Dictionary Time Complexity

Searching a dictionary takes O(1) time not O(n) and that is why Dictionaries are better than lists

This is an excellent question. It feels counterintuitive: if you have a box of 10 items, finding one is quick. If you have a box of 10 million items, finding one should take much longer, right?

That is exactly how a regular list works (which is $O(n)$ time). But a Python dictionary does not search through its items one by one. Instead, it uses a brilliant computer science trick called a Hash Table.

Here is how dictionaries skip the line and find your data instantly, regardless of size.

The Library vs. The Filing Cabinet Analogy

Imagine you are looking for a specific book in a library that has 10,000 books scattered everywhere.

• The $O(n)$ List Method: You walk around and check every single book’s title until you find yours. If the library gets bigger, it takes longer to search.

• The $O(1)$ Dictionary Method: You walk up to a magical librarian. You say the title of the book. The librarian performs a quick mental calculation and says, “Aisle 4, Shelf 2, Position 8.” You walk straight there and grab the book.

It didn’t matter if the library had 10 books or 10 million books. The librarian’s calculation took the exact same amount of time, and walking to the specific spot took the exact same amount of time.

How Python’s “Magical Librarian” Works

Under the hood, a Python dictionary is built using an array (a contiguous block of memory). Arrays have a special property: if you know the exact numerical index (e.g., array[452]), the computer can go directly to that exact spot in memory instantly. That is $O(1)$ time.

But dictionary keys aren’t usually numbers like 452; they are strings, objects, or tuples (like "apple" or "start_island").

So, how do we turn a word into an exact memory location?

Step 1: The Hash Function

When you run links["island_A"] = "island_B", Python takes the key ("island_A") and passes it through a hash function.

A hash function is a mathematical algorithm that scrambles data into a seemingly random, but perfectly consistent, integer.

For example (conceptual numbers):

• hash("island_A") might output 8239048123

• hash("island_B") might output 9928173461

Step 2: Finding the Index

Python takes that massive hash number and uses the modulo operator (%) against the current size of the dictionary’s underlying array to find a valid index.

Let’s say the dictionary’s array currently has 8 slots.

• 8239048123 % 8 = 3

Python now knows: Put “island_B” in slot 3.

Step 3: Instant Lookup

Later, when your code asks: if "island_A" in links:

1. Python runs "island_A" through the hash function again. It gets the exact same number: 8239048123.

2. It calculates the index: 8239048123 % 8 = 3.

3. It looks directly at memory slot 3.

It didn’t search slots 0, 1, 2, 4, 5, 6, or 7. It went straight to 3. This three-step process takes the exact same amount of time whether the dictionary has 8 slots or 8 million slots. Therefore, it is $O(1)$ (Constant Time).

The Only Catch: Hash Collisions

You might be wondering: What if two different keys calculate to the same slot? (e.g., what if "island_C" also results in slot 3?)

This is called a Hash Collision. Python handles this gracefully. If slot 3 is already taken by "island_A", Python uses a specific formula to jump to a new, empty slot (this is called open addressing or probing).

When a dictionary gets too full (usually about 66% full), collisions happen too often, which would slow things down. To prevent this, Python secretly creates a brand new, much larger array in the background, recalculates the slots for all existing items, and moves them over.

Because Python keeps the dictionary relatively spacious, the chances of collisions remain low. The math guarantees that, on average, finding a key will only take one or two immediate jumps, maintaining that lightning-fast $O(1)$ speed even as the dictionary grows massive.