1. (a) There were two different ways to answer this, depending on some details of your assumptions. The intended model was that the priority of an item was stored on an object representing the item, and that the priority queue was represented just as a list of items; therefore, a find-minimum operation would take time proportional to the number of items, but a decrease-priority operation could be performed in constant time. With this assumption, the time is O(t^4): there are O(t^2) find-min operations taking O(t^2) time each, and O(t^3) decrease-priority operations taking O(1) time each.

An alternative assumption used by some of the students was that the priority queue was stored as an unordered list of (item,priority) pairs, and that there was no extra information that could be used to link an item to the location of its pair in this list, so that decrease-priority operations would also take time proportional to the number of items. With this assumption, the time is O(t^5).

(b) O(t^3 log t).

(c & d) The correct choice is the one that balances the time for delete-minimum operations, O(d t^2 log_d t^2), with the time for decrease-priority operations, O(t^3 log_d t^2). Therefore, we should set d=t; with this choice, log_d(t^2)=2, a constant that goes away when we use O-notation, so the total time is O(t^3). We could also get O(t^3) time by setting d=t^c for any constant c between 0 and 1.


2. The Vector is rebuilt, at a cost of O(N) time, every K insertions. Therefore, the time per insertion is O(N/K) = O(N).


3. (a) The time per insertion is the actual time, O(log n), plus the change to Phi, which is ((n+1) log(n+1)) - (n log n) = O(log n). Adding these two gives O(log n).

(b) The time per deletion is the actual time, O(log n), plus the change in Phi, which is (n log n) - (n-1) log (n-1), approximately -log n. Therefore the actual time is cancelled by the negative change to Phi, giving constant amortized time.