Time Complexity: Collision Handling Using Open Addressing Linear Probing
O(n)
0
0
Collision Handling Using Open Addressing Linear Probing in DSA Python - Time & Space Complexity
Understanding Time Complexity
When we use open addressing with linear probing to handle collisions in a hash table, we want to know how long it takes to insert or find an item.
We ask: How does the time grow as the table fills up?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def insert(self, key):
index = key % self.size
while self.table[index] is not None:
index = (index + 1) % self.size
self.table[index] = key
This code inserts keys into a hash table using linear probing to find the next empty slot when a collision happens.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The while loop that checks for the next empty slot when a collision occurs.
- How many times: In the worst case, it can check almost all slots if the table is nearly full.
How Execution Grows With Input
When the table is mostly empty, the loop runs very few times. As the table fills, the loop runs more times to find an empty slot.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 (10% full) | About 1 check per insert |
| 100 (50% full) | Several checks per insert |
| 1000 (90% full) | Many checks, close to 1000 in worst case |
Pattern observation: The more full the table, the longer it takes to find an empty slot, growing roughly linearly with the number of filled slots.
Final Time Complexity
Time Complexity: O(n)
This means in the worst case, the time to insert or search grows linearly with the number of items in the table.
Common Mistake
[X] Wrong: "Insertion always takes constant time because hashing is constant time."
[OK] Correct: When collisions happen and the table is full or nearly full, linear probing must check many slots, making insertion slower.
Interview Connect
Understanding how collision handling affects time helps you explain trade-offs in hash tables clearly and confidently during interviews.
Self-Check
"What if we changed linear probing to quadratic probing? How would the time complexity change?"