# [racket] Looking for feedback on code style

Will M. Farr wrote:
>* Looks like Phil beat me to it, but here's some code that finds the
*>* n-th element of a list in O(N) time. The algorithm is similar to
*>* quicksort, but you don't sort both the sub-lists: partition the list
*>* into elements less than and greater or equal to a pivot. By counting
*>* the number of elements less than the pivot, you know whether the one
*>* you're looking for will be found in that set, or in the greater or
*>* equal set. Repeat the search in the appropriate set. The partition
*>* takes O(N) time. On average, it cuts the number of elements searched
*>* in half each time, so we have
*>*
*>* total time = N + N/2 + N/4 + ... = 2*N as N --> infty
*
Not quite. Consider the case of the median. If the pivot is the smallest
element, the recursion is on N-1 elements. If the pivot is the second
smallest, on N-2; and so on. If the pivot is the median, you can stop
(not all provided code does this, but it doesn't matter much for the
analysis). But the situation is symmetric on the other side: if the
pivot is the largest element, the recursion is on N-1 elements, and so
on down. So the expected number of elements the recursion is performed
on is about 3N/4.
And then what? Are we justified in saying T(N) = T(3N/4) + O(N)? Really,
we have T(N) = T(X) + O(N), where X is a random variable uniformly
distributed over [0..N-1]. With a suitable induction hypothesis, we can
dig ourselves out of this, but it's not simple, unfortunately. --PR