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 modifications affect the running time for successful searches, unsuccessful searches, insertions, and deletions?

Professor Marley is a quack who has no idea what they’re talking about:

• Successful searches still take \(\Theta(1 + a)\). Having a sorted linked list doesn’t change our performance since traversal is still sequential.

• Unssucessful search might be faster, but not by much. We can terminate a search once our current element exceeds the target value which can cut down on the amount of searching required. So still \(\Theta(1 + a)\) with a smaller constant facter.

• Insertion will take longer since we need to find the correct position to maintain sorted order of our linked lists. So \(\Theta(1 + a)\) rather than \(\Theta(1)\).

• Deletion remains unchanged since we still need to find the targeted element in the linked list, sorted as it may be. \(\Theta(1 + a)\) as before.

I move that we strip Professor Marley of their title and dismiss them from their post in disgrace.