On Mon, Jul 1, 2013 at 4:31 PM, Claudio Freire <klaussfre...@gmail.com> wrote: > What? > > A median of medians algorithm will guarantee floor(N/2) elements on > the smaller. That's the definition of median. > > Note that I'm referring to picking the actual median of all tuples, > not just a sample. That's slow, but it guarantees O(n log n).
Ah, OK. Well, yes, that would guarantee O(n lg n). But, as you say, it would be slow. :-) -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (email@example.com) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers