<a href="http://programmingpraxis.com/2009/12/11/selection/">http://programmingpraxis.com/2009/12/11/selection/</a><br><br><div class="gmail_quote">On Thu, Sep 9, 2010 at 10:26 AM, David Van Horn <span dir="ltr"><<a href="mailto:dvanhorn@ccs.neu.edu">dvanhorn@ccs.neu.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">On 9/9/10 10:04 AM, Prabhakar Ragde wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I don't think vectors help very much in this case (median-finding). For<br>
the given code, the O(n) access to the middle of the list is dominated<br>
by the cost of the sorting, which is at least O(n log n) [*].<br>
<br>
It is theoretically possible to compute the median in O(n) time, but the<br>
method is complicated and not very practical. But sorting definitely<br>
does too much work. If only the median (or the kth largest, a problem<br>
called "selection") is needed, a method which is both practical and of<br>
pedagogical interest stems from adapting Quicksort, which is a good<br>
exercise after section 25.2 of HtDP. This has expected cost O(n) on<br>
random data, and vectors offer no asymptotic advantage over lists. --PR<br>
<br>
[*] Technically, "at least Omega(n log n)".<br>
</blockquote>
<br></div>
The original post got me interested in median algorithms and I started to read up on the selection problem. Wikipedia (I know, I know) says the same thing as you: medians can be computed in O(n) time and points to selection as the way to do it. But I don't see how to use selection to achieve a O(n)-time median algorithm -- selection (of the kth largest/smallest element) is O(n), but that's were k is some fixed constant. To compute the median, you let k=n/2 (right?), so it's no longer constant. Can you point me to (or sketch) a O(n) method? Or just correct me if my reasoning is going astray.<br>
<br>
Thanks!<br><font color="#888888">
<br>
David</font><div><div></div><div class="h5"><br>
_________________________________________________<br>
For list-related administrative tasks:<br>
<a href="http://lists.racket-lang.org/listinfo/users" target="_blank">http://lists.racket-lang.org/listinfo/users</a><br>
</div></div></blockquote></div><br>