Root Root - 1 year ago 73
Python Question

Why has an unsuccessful search time for a hash table a time complexity Θ(1+α)?

I get the Θ(1) part is the time that uses to calculate hash table, but I don't understand the Θ(α) part.

In my view, the time complexity is Θ(n). Assume α is the expected length and the table has m slots. To ensure the key is not in the table, we need to search each slot, and each slot has α excepted length, so the total time is α times m, then it's Θ(n).

Could anyone tell me which part I didn't understand correctly?

Answer Source

Testing if a given key is in the hash table doesn't need to test all slots. You simply calculate the hash value for the given key (1). This hash value identifies which slot the key has to be in, if it is in the hash table. So, you simply need to compare all entries (α) in that slot with the given key, yielding Θ(1+α). You don't need to look at the other slots because the key cannot be stored in any of the other slots.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download