The following is a question from the textbook Introduction to Algorithms, however a solution to the problem is not given...

Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor’s modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?

For this question I believe the running time would be the same for searching if the list are sorted, because they are linked lists, and one still needs to traverse the entire list in order to find a value.

For inserting however, it would take longer because one can't just insert a value to the head of the list because the order must now be preserved. It would no longer be $O(1)$ I believe.

For deletion I have no idea.

In fact, I'm not quite sure if any of my answers are correct, can someone please help me out here?

  • $\begingroup$ You don't necessarily need to keep your chain as a linked list. You can have it as an array, in which case if the elements were sorted you could speed up lookup within a chain of n items to O(logn) with binary search. $\endgroup$ – Francesco Gramano Feb 24 '15 at 21:32
  • $\begingroup$ You don't post a specific question. Hint for finding one: take the analyses you have seen in lecture or find in your textbook and try to adapt them to the proposed variant. ("Nothing changes" is a valid answer! Be mindful of exact vs asymptotic, and worst-case vs average-case runtimes, though.) $\endgroup$ – Raphael Feb 24 '15 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.