Collision Handling Using Open Addressing Linear Probing in DSA C - Time & Space Complexity

Time Complexity: Collision Handling Using Open Addressing Linear Probing

O(n)

Understanding Time Complexity

We want to understand how long it takes to insert items when collisions happen in a hash table using linear probing.

How does the time to find a free spot grow as the table fills up?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int linearProbingInsert(int hashTable[], int size, int key) {
    int index = key % size;
    int startIndex = index;
    while (hashTable[index] != -1) { // -1 means empty
        index = (index + 1) % size;
        if (index == startIndex) {
            return -1; // Table full
        }
    }
    hashTable[index] = key;
    return index;
}
    

This code tries to insert a key into a hash table using linear probing to handle collisions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that checks each slot until an empty one is found.
• How many times: In the worst case, it can check every slot once if the table is almost full.

How Execution Grows With Input

As the table fills, the number of checks grows because more slots are occupied.

Input Size (n)	Approx. Operations
10 (mostly empty)	1-2 checks
100 (half full)	5-10 checks
1000 (almost full)	up to 1000 checks

Pattern observation: The more full the table, the longer it takes to find an empty slot, growing roughly linearly with table size.

Final Time Complexity

Time Complexity: O(n)

This means in the worst case, the time to insert grows directly with the number of slots in the table.

Common Mistake

[X] Wrong: "Insertion always takes constant time because we just compute the hash once."

[OK] Correct: When collisions happen, we may need to check many slots, so insertion time can grow with table fullness.

Interview Connect

Understanding how collision handling affects insertion time helps you explain trade-offs in hash table design clearly and confidently.

Self-Check

"What if we changed linear probing to quadratic probing? How would the time complexity change?"