**k-Selection**

Given find the largest element.

**A quicksort like approach**: Pick a pivot and partition into two arrays and . If then recursively find the largest element in , otherwise recursively find largest element in . If and . Then the recurrence relation becomes . We have the following two cases:

*is arbitrary*: In the worst case could be as small as . Then we have and so .*is picked randomly*: Let denote the expected time taken on the list of size . Then for some constant . We observe that . To solve the recurrence, we guess that for some constant . We claim that choosing suffices. Plugging this into the recurrence, we get . Thus .

**A better choice of pivot**:

- Divide the list into groups of elements
- Find the median for each group of elements, let them be .
- Find median of recursively; let it be .
- Use as a pivot to partition
- Recurse on appropriate side

Let be the time to run **k-select** on a list of size . Then step takes , while we claim in the worst case the size of the largest partition is at most . This is because the number of elements smaller than are all the such that as well as all elements in the list smaller than each of these . Thus the number of elements smaller than is atleast and so the number of elements larger than is atmost . The recurrence relation is therefore . Let us guess for some constant . Thus setting suffices, giving us a running time of .

I found this useful for illustrating the deterministic k-selection algorithm.

http://web.mit.edu/~neboat/www/6.046-fa09/rec3.pdf