In accordance with my instructions, I have given birth to twins in the enclosed envelope.

1. For each pair of functions, determine which are O() of the other, and which are of the other (if any).
   1. and
   2. and
   3. and
   4. and
2. Professor Truckon claims to have developed a new data structure based on key comparisons that performs insert and delete in time , decrease-key in time , and delete-min and min in O(1). Why isn't the professor getting the best performance possible out of the data structure?
3. Professor Truckon claims to have developed a new data structure based on key comparisons that performs insert, decrease-key, and delete in time , delete-min in time and min in . Why doesn't the professor have a good research result?
4. Professor Truckon claims to have developed a new data structure based on key comparisons that performs decrease-key and delete in time , insert in time , and delete-min and min in . Why does the professor's claim appear incorrect?
5. Write a recurrence for binary search.
6. Derive the recurrence for the average behavior of quicksort, that is, You may use facts about the best case of quicksort and the distribution of sizes created by partition, but state the facts clearly.
7. Solve the recurrence .
8. Prove that makeheap takes O(n) time. You may assume that Heapify takes logarithmic time.
9. Suppose your computer environment supports a sort of 4 elements in a single step. Prove that the lower bound on comparison sorts is still valid in this environment.
10. Consider input of 3 arrays of n elements each. Each array is sorted. Find the best bounds you can on the number of comparisons required to merge these into one sorted list.

• About this document ...