DECISION TREE LOWER BOUND. We are given 3n + 2 distinct numbers and are asked to find the (n+1)-st and (2n + 2)-nd smallest using a binary oracle.

(i) Derive the decision tree lower bound for this problem (exactly-not in big oh notation).

(ii) Show that as no, the lower bound is cn for some constant c (where means that the ratio of left and right-hand-side tends to one), and determine c.