Printable View
Given an Hashtable, is there a way of finding the maximum element in the hashtable in less than O(n) in the worst case where n is the total number of elements in the Hashtable? In other words, is there a way of finding such an element by means other than doing a linear search?
HM
A hashtable is unordered, so there is no way to do it faster than O(n).
Depends on the function used for hashing. Also depends on the no of digits of the integers we are using. Typically - a radix sort uses this. Worst case is still O(kN) but think of the best case.