Practice Exercises: Solving Recurrences, Sorting

Exercise 1

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$

Exercise 2

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)$.

Exercise 3

Assume that algorithm $A$ and algorithm $B$ both solve the same problem. In the worst case algorithm $A$ takes $T_A(n)$ steps and algorithm $B$ takes $T_B(n)$ steps with $T_A(n) \in \Theta(n)$ and $T_B(n) \in \Theta(\sqrt{n})$. Does that imply that algorithm $B$ always takes fewer steps than algorithm $A$ for any input of size $n$? And does it imply $T_B(n) \leq T_A(n)$ for all $n$? Explain your answer.

Exercise 4

Given a set $S$ of $n$ integers and another integer $z$ we want to find two elements $x,y \in S$ such that $x \cdot y = z$, or report that no two such integers (in $S$) exist. Give an algorithm for this problem that runs in $O (n \log n)$ time.

Exercise 5

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.