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 .