Find maximum element in hashtable with doubly linked list in each slot


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 m.

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.


Show source
| search   | algorithm   | hashtable   2016-12-20 05:12 1 Answers

Answers ( 1 )

  1. 2016-12-20 05:12

    Slots can be empty (have no elements in the list). You have to iterate all the slots to find all the non-empty lists, so that's O(m) work. Then you have to search all the lists, which is O(n) work. Total work: O(n + m).

◀ Go back