On Sat, Aug 1, 2015 at 9:49 AM, Jeremy Harris <j...@wizmail.org> wrote: > On 31/07/15 18:31, Robert Haas wrote: >> On Fri, Jul 31, 2015 at 7:21 AM, Jeremy Harris <j...@wizmail.org> wrote: >>> Heapification is O(n) already, whether siftup (existing) or down. >> >> That's not my impression, or what Wikipedia says. Source? > > Measurements done last year: > > http://www.postgresql.org/message-id/52f35462.3030...@wizmail.org > (spreadsheet attachment) > > http://www.postgresql.org/message-id/52f40ce9.1070...@wizmail.org > (measurement procedure and spreadsheet explanation)
I don't think that running benchmarks is the right way to establish the asymptotic runtime of an algorithm. I mean, if you test quicksort, it will run in much less than O(n^2) time on almost any input. But that does not mean that the worst-case run time is anything other than O(n^2). -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
