ExamCompetition Your Success, Our Mission
Login Register
Question discussion

In a hash table that resolves collisions by separate chaining, let the load factor be α = n / m. Under simple uniform hashing, the expected…

2341Medium DSSSB TGT Computer Science 0 replies 1 views
0

In a hash table that resolves collisions by separate chaining, let the load factor be α = n / m. Under simple uniform hashing, the expected time of an unsuccessful search is

  • AΘ(log n)
  • BΘ(n)
  • CΘ(1 + α)
  • DΘ(α²)
Correct answer: C

Explanation

The key hashes to a chain of expected length α, which must be scanned completely, giving Θ(1 + α) including the time to compute the hash.
Join the discussion Report an error

Discussion 0

Nobody has replied yet. Start the discussion!