Introduction

In Python, dict.pop(key) is usually an O(1) operation on average. That answer comes from the fact that Python dictionaries are hash tables, so lookup and deletion by key are typically constant-time. The important nuance is that this is an average-case statement, not a worst-case guarantee.

Why pop Is Usually O(1)

A dictionary stores keys by their hash value. When you call pop, Python hashes the key, locates the corresponding slot, removes the entry, and returns the value.

1scores = {"alice": 90, "bob": 84, "carol": 95}
2removed = scores.pop("bob")
3
4print(removed)
5print(scores)

For normal workloads with a healthy hash distribution, this is constant-time on average. The dictionary does not scan every key to find the match.

That is why insertion, lookup, and deletion by key are commonly described as average O(1) operations for Python dictionaries.

Worst-Case Complexity Is Higher

The worst case can degrade toward O(n) if many keys collide into the same probing pattern or the table becomes pathological. In practice, Python's dictionary implementation is engineered to make these cases uncommon, but they are still part of the theoretical complexity discussion.

So the honest answer is:

• average case: O(1)
• worst case: O(n)

That distinction is standard for hash-table-based structures.

The Default Argument Does Not Change the Big-O

pop optionally accepts a default value.

config = {"host": "localhost"}
port = config.pop("port", 5432)
print(port)

If the key exists, Python removes it and returns its value. If the key does not exist, it returns the default instead of raising KeyError.

This does not fundamentally change the time complexity. Python still performs a hash-table lookup, so the average behavior remains O(1).

popitem() Is a Different API

It is worth separating pop(key) from popitem(). popitem() removes and returns one item, typically the most recently inserted key-value pair in modern Python versions.

1data = {"a": 1, "b": 2, "c": 3}
2item = data.popitem()
3print(item)
4print(data)

This is also effectively constant-time in normal use, but the semantics differ. pop(key) removes a specific key, while popitem() removes an arbitrary or insertion-ordered item depending on the language version.

Practical Performance Considerations

Big-O notation describes growth, not exact runtime. In real code, the actual speed of pop still depends on factors such as key hashing cost, cache behavior, dictionary size, and how often resizes occur elsewhere in the workload.

For example, a short string key and a large custom object key may both give you average O(1) lookup, but the constant factors are different because computing the hash and comparing equality can cost more.

That does not change the asymptotic classification, but it does matter when you profile real programs.

Common Pitfalls

A common mistake is stating that dictionary operations are always O(1) with no qualification. That is fine for quick intuition, but incomplete if you are discussing algorithm analysis seriously. The average-case assumption is important.

Another mistake is confusing pop complexity with the cost of iterating over a dictionary to find a value by condition. pop by key is usually constant-time. Searching for a value based on a predicate is a different problem and can be linear.

Developers also sometimes ignore the cost of hashing. If the key type has an expensive __hash__ or __eq__ implementation, the practical runtime of dictionary operations can be noticeably higher even when the theoretical average remains O(1).

Finally, remember that pop mutates the dictionary. If you only need the value and want to keep the entry, use direct indexing or get instead.

Summary

• 'dict.pop(key) is average-case O(1) because Python dictionaries are hash tables.'
• The worst case can degrade to O(n) in pathological collision scenarios.
• Providing a default value to pop does not change the asymptotic complexity.
• 'pop(key) and popitem() are related but semantically different operations.'
• Big-O tells you the growth class; real runtime still depends on hashing and implementation details.