## COMP 731 - Assignment 2 - Due Thursday, 13 July 2000

- Prove that if
*f* is Theta(*n*) and
*g* is *O(n)* then *f*+*g* is Theta(*n*).

- Find a sequence of 10 integers such that Mergesort takes the maximal
number of possible comparissons to sort your sequence of numbers.
Now do it for 15 numbers.

- We have described two different procedures to build a heap:
repeated insertion, starting from the empty heap; and fixing up each
subtree, processing elements
*n*, *n*-1, ..., 2, 1.
Do these two methods always result in same heap?
Prove that the do, or provide a counterexample to show that the do not.

- Solve the following recurrence relations to within Theta() accuracy.
Assume T(n) = Theta(1) for sufficiently small n.
- T(n) = 5T(n/5) + n - lg n
- T(n) = 2 T(n/2) + n lg n
- T(n) = n T(n-1)
- T(n) = n + T(n-1)
- T(n) = n^2 + T(n-1)