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?