Give asymptotic upper and lower bounds for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for $n \leq 2$. Make your bounds as tight as possible, and justify your answers.

(a) $T(n) = 7T(n/2) + n^2$

(b) $T(n) = 7T(n/3) + n^2$

(c) $T(n) = 2T(n/4) + \sqrt n$

(d) $T(n) = T(n-1) + n$

(e) $T(n) = 4T(n/2) + n^2 \sqrt n$

Use substitution method to prove that the solution of

$$T(n) = \begin{cases} 1 &\mbox{if } n = 1 \\ T(\lceil n/2 \rceil) + 1 & \mbox{if } n >1\end{cases}$$is $O(\log n)$.

Suppose you have a set $S$ of $n$ numbers, and suppose that given two elements of $S$ you cannot determine which is larger. However, you are given an oracle that will tell you the median of a set of three distinct elements from $S$.

(a) Give a linear time algorithm to find the pair of the largest and the smallest number in $S$.

(b) Give an algorithm to sort $S$ in $O(n \log n)$ time. You are allowed one regular comparison, otherwise you need to rely solely on the oracle.