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

6 Years
Discussion Span
Last Post by raptr_dflo

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?


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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.