What is the asymptotic cost of looking up a key in a table by direct access?
A)O(1)
B)O(logn)
C)O(nlogn)
D)O(n)
You can consider option A) O(1) because in a table average time complexity for searching a key in O(1) and amortized. In the worst case, time complexity may be O(n). This worst-case happens when all the elements are hashed into the same position, in that case, we have to search all the elements present in that position, which in turn produces a time complexity of O(n). But mostly good hash functions are used to hash data into as different positions as possible, in other words, scatter the data uniformly among its address space., So, it’s very rare to happen such an incident where all the elements are in the same position. So, you can consider O(1) as correct answer in this question
Recent Comments