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
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
