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:

Reply via email to