What is the worst-case time complexity of searching in a hash table?

Options

  • A. O(1)
  • B. O(log n)
  • C. O(n)
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

C. O(n)

Detailed Explanation

Although hash tables provide O(1) average search time, their worst-case search complexity can be O(n). This can happen when many keys collide and end up in the same bucket or when probing becomes highly inefficient. In separate chaining, a very long chain can require scanning many elements. With a good hash function, appropriate table sizing, and controlled load factor, such severe collision patterns are generally reduced and average performance remains close to constant time.
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts