The other problem people had major difficulties
with was problem 5.

====
5. (8 points total) Suppose H1 and H2 are heaps.
H1 has n items, and H2 has m items.  Pseudocode
for an algorithm to merge the two heaps into a
new heap H3 consisting of the n+m items in H1 and H2
might look like this:


copy H1 to H3;  // H3 now looks just like H1
for (int i = 0; i < m; i++)
{
  x = H2.deleteMin();
  H3.insert(x);
}

a. (4 points)  If all the heaps are implemented as
binary heaps, how long will this algorithm take?
(Use Big-Oh notation.)

b. (4 points)  Could there be an advantage, compared
to the above pseudocode, in copying H2 into H3 and
then inserting elements from H1 to H3?  (As in part a,
assume the heaps are binary heaps.)  Why or why not?
====

This problem was a direct application of the running
time analysis techniques we have studied all quarter.
I thought these were easy points, but for some reason,
it turned out to be difficult.

a.
It takes O(n) time to copy H1 to H3 (just a direct
copy of the elements of the array used to represent
H1 into the array used to represent H3).

The for loop iterates m times (once for each element
in H2).  Inside the loop, the deleteMin() operation
takes O(log M), since the maximum size of H2 is m.
The insert() operation takes O(log(n+m)), since the
maximum size of H3 is n+m.

So, the total time spent in the loop is
O(m * (log m + log(n+m))) = O(m * log(n+m)).

This means the total running time of the entire pseudocode
is O(n + m log(n+m)).

b. If the roles of H1 and H2 are switched so that we
copy H2 into H3 first and then insert elements from H1
into H3, then the running time for the corresponding
pseudocode:

copy H2 to H3;  // H3 now looks just like H2
for (int i = 0; i < n; i++)
{
  x = H1.deleteMin();
  H3.insert(x);
}

would be O(m + n log(m+n)).  Note that the m and n have
switched places in the analysis.

Now let's compare n + m log(m+n) to m + n log(m+n).
In fact, we want to ask when is
  n + m log(m+n) - ( m + n log(m+n) ) > 0 ?
Whenever the quantity on the left is greater than zero,
then the algorithm in part a takes longer than the
algorithm in part b.

After some algebraic manipulation, we get for the left side:
  (n-m) + (m-n) log(n+m) = (m-n) (log(n+m) - 1)

So, if n is smaller than m, then the algorithm in part b
is faster.

One small detail.  The big-Oh notation hides constant
factors, so n might need to be a lot smaller than m for
the algorithm to be faster, but I think the constant
factors hidden in the big-Oh are the same for the two
algorithms, so in fact n < m is a precise characterization
for when part b's algorithm is faster.