Problem
For each of the cases below, explain how the proposed change will impact the expected running time for insertion, deletion, successful, and unsuccessful search. Use Θ-notation. However, if the Θ bound is unchanged, say how the constant inside the Θ changes (or say that the constant does not change). In other words, say how much of a real effect you would see. For delete, assume you have already searched for and found the item you will delete. Give your answers in terms of n and m and be sure to provide justifications.
i. Suppose we modify hashing with chaining to keep all the chains in sorted order.
ii. Suppose we are using hashing with chaining, but instead of a linked list we have a balanced BST at each cell of the hash table.