Assuming it is possible to sort n numbers in O ( n log n ) time, show that it is possible to solve the three-way set disjointness problem in O ( n log n ) time.   Describe an efficient algorithm for...

Assuming it is possible to sort
n
numbers in
O(nlog
n) time, show that it

is possible to solve the three-way set disjointness problem in
O(nlogn)

time.

Describe an efficient algorithm for finding the ten largest elements in a

sequence of size
n. What is the running time of your algorithm?

Show that logb f
(n) is (log
f
(n)) if
b
> 1 is a constant.

Describe an algorithm for finding both the minimum and maximum of
n

numbers using fewer than 3n/2 comparisons. (Hint: First, construct a

group of candidate minimums and a group of candidate maximums.)