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

Question

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.

Thanks.

Show source

## Answers ( 1 )

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