Question

suppose we have a hash table which uses linear probing which is full and needs to be expanded. what is the worst case time complexity of expanding the hash table, assuming that hash functions are o(1)? (a) o(1) (b) o(log n) (c) o(n) (d) o(n log n) (e) o(n^2)

Answer 1

The time complexity for expanding a full hash table using linear probing is O(n), as each of the n elements needs to be rehashed and inserted into a new larger table.

Step-by-step explanation:

When expanding a hash table that uses linear probing and is full, we need to allocate a larger table and rehash every existing element into this new table. Since we have to rehash each element, and assuming the hash function is O(1), the time complexity is determined by the number of elements n in the table. Every element must be visited and inserted into its new position in the expanded hash table. Consequently, the time complexity for expanding the full hash table is O(n), where n is the number of elements in the table.