order of deletion of a node in hashing

[starkk]

In chain hashing how can the order of deleting a node in double linked list be O(1) it should first check for the slot which is of O(1)and then it should check for the element to be to be removed in the linked list pointed by that slot which is of order O(n) in the worst case and O(n/m)in avg case considering n total elements and m slots.so the total so the total order of deletion should be O(n/m) which is the same when we implement with singled linked lists.Then,what is the use of double linked list and how will the order for deletion be O(1) as the text book suggests...

some one help me pls..

[Narue]

Perhaps the book means amortized O(1) instead of per operation O(1). Though that's the same for single linked lists, so I can't say why your book makes a distinction. Which book is it?

[starkk]

introduction to algorithms by cormen

[raptr_dflo]

Perhaps the author's intent is: the complexity of finding the node to delete is O(n/m) (on average), but once found, the complexity of deleting that node is O(1)? Since I don't own a copy of the book, and you didn't explicitly quote the author, I can't be sure.

There is a listing of known errata available on his website -- you'll need the edition and printing of your book, and page number of the suspected error, to see if it's already been reported.