O(n^2), again, now in Windows Management Instrumentation

Re:O(n^2), again, now in Windows Management Instrumentation by chx on Monday December 09, 2019 @04:49PM (#21746996)

> which a sort should never be

There's certainly a most awesome sort algorithm which is exponential...

https://www.dangermouse.net/esoteric/bogobogosort.html

They are not even sure what the complexity is but it's like O(n!^(n-k)) or O(n*(n!)^n).

[ Parent | on HN ]

Re:O(n^2), again, now in Windows Management Instrumentation by vecter on Monday December 09, 2019 @05:28PM (#21747350)

I'm aware of bogosort and its crazy variants, but let's not be ridiculous here. You could make any "sorting" algorithm arbitrarily bad if you'd like by doing such silly but useless things.

[ Parent | on HN ]

Re:O(n^2), again, now in Windows Management Instrumentation by samatman on Monday December 09, 2019 @09:39PM (#21749117)

I propose Boltzmann sort: wait around until the heat death of the universe, and a Boltzmann brain will emerge from the cosmos, and sort your values while contemplating infinity.

[ Parent | on HN ]

Re:O(n^2), again, now in Windows Management Instrumentation by thewakalix on Tuesday December 10, 2019 @02:25AM (#21750408)

Ah, a fully general O(1) algorithm. Amazing.

[ Parent | on HN ]

Re:O(n^2), again, now in Windows Management Instrumentation by Graham24 on Tuesday December 10, 2019 @10:17AM (#21753213)

The very idea of O(n*(n!)^n) is going to give me nightmares.

[ Parent | on HN ]