What is the average time complexity of searching for an element 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)

A. O(1)

Detailed Explanation

The average time complexity of searching in a hash table is O(1), assuming a good hash function and controlled collisions. The key is passed through the hash function to determine the likely storage location. Therefore, the desired element can normally be accessed directly rather than scanning every element. However, in the worst case, many keys may collide at the same location, making searching O(n). Hash-table performance therefore depends heavily on hashing quality and collision management.
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts