Lower bound på sammenligninger

Opgave tekst: Consider algorithms which should do all of the following for a list of 2n+ 3 elements:
?nd the largest element, ?nd the smallest element, ?nd the median element, and
partition the remaining 2n elements into two sets, each of size n, such that the
smallest n elements are all in the ?rst set and the largest n elements in the second
set. Suppose the algorithm can be modelled by decision trees which have as their
basic operations a comparison operation which can compare two elements, telling
which is larger.

(a) Use an information theoretic argument to prove a lower bound on the number
of these comparisons any such algorithm would need to make. How many leaves
does your tree have and what is the degree of each node in the tree? (You will
need to approximate – give a lower bound.)

(b) Give a linear time algorithm for solving this problem (?nding the required three
elements and doing the partitioning) and analyze your algorithm.

på forhånd tak for hjælpen!!