CS 146: Homework due 2/1
In class, we saw two methods for finding the maximum item from a set,
and discussed how these might be extended to find the second largest
item as well. Assume that you are given n distinct integers.
Answer the following questions for each of the two methods and their
extensions.
- In the worst case, how many comparisons are needed to find the
maximum item?
- In the best case, how many comparisons are needed to find the
maximum item?
- In the worst case, how many comparisons are needed to find the
2nd maximum item?
- In the best case, how many comparisons are needed to find the
2nd maximum item?
- In the worst case, how many comparisons are needed to find the
3rd maximum item?
- In the best case, how many comparisons are needed to find the
3rd maximum item?
In each case, you must do enough comparisons to be positive that your
solution is in fact the correct item. That is, you cannot just return
an arbitrary item, with no comparisons, hoping that "in the best case"
it will turn out to be the requested item.
If needed, you may assume that n is of a special form, such as
n=2i, for integer i. (Bonus for the correct
answer for general n.)
Note: in finding the 2nd largest
item, assume that you are also finding the first largest. In finding
the 3rd largest, assume that you are also finding the largest 2nd
largest items.
You should (informally) describe your algorithm "extensions" to
find the 2nd and 3rd largest items, but not the the point of code or
pseudo-code. That is, after finding the maximum item, extra
comparisons will be needed to find the 2nd maximum item. You do not
need to give code to determine which elements will be compared, merely
describe them, similar to the way we did in class.