# Homework 2

Due Wednesday, January 22 at 5:00 PM. Please refer to the homework policy here.

1. Use the recursion tree method to solve the following recurrence.

2. Given an array $A$ of integers length $n$, and some integer $k$, design and analyze an algorithm that finds the $k$ smallest elements in $O(n \log k)$ time.

3. Recall from class the randomized algorithm quick-sort, which sorts a list of numbers in $O(n \log n)$ expected time. In this problem, we design a similar problem for selecting the median, or more generally, the rank $k$ element (i.e., the $k$th smallest element), from an array of numbers.

We take as input an array of integers $A[1..n]$. Given an index $k$ between 1 and $n$, the goal is to find the $k$th largest number in $A$. Note that $A$ is not sorted. One simple $O(n \log n)$ time algorithm is to sort $A$, and return the $k$th number in the sorted list. Our goal is to do better.

The high level algorithm is similar to quick-sort. Each iteration we pick a random number in the array as a pivot, and divide the array into the set of numbers smaller than the pivot, and the set of numbers larger than the pivot. Then we will know the rank of the pivot in the array, and be able to deduce if the number we are looking for is either smaller than the pivot, equal to the pivot, or to the right of the pivot. Then we can recurse appropriately.

1. Give a pseudocode implementation of the randomized selection algorithm described above.
2. Show that this randomized selection algorithm takes $O(n)$ time in expectation.