There is a hash table, slots in an array, each slot has a doubly linked list, unsorted.
Total element count is
n, slot count is
What is the time complexity to:
- Find the maximum element in whole hashtable.
- Find the successor element for a given element x.
They should be both
O(n), right? Because you have to iterate every element.
But, in the book
<The algorithm design manual 2nd>, page 90, it says it's
O(n+m), but I don't get it.
Anyone, help to tell which is right? And, why.