News for hackers. Stuff that matters.

A comment on O-notation considered harmful (use Analytic Combinatorics instead). Parent comment

Re:O-notation considered harmful (use Analytic Combinatorics... by praptak on Sunday February 10, 2013 @04:46PM (#5198061)
Same goes for any implementation of quicksort with deterministic choice of pivot. It is possible to construct a DoS-type permutation to make it quadratic.

> O(n^2) means very slow very quickly.

You mean Theta(n^2) :-)

[ Parent | on HN ]
Re:O-notation considered harmful (use Analytic Combinatorics... by Derander on Sunday February 10, 2013 @06:26PM (#5198430)
If we're being really picky it is possible to deterministically find the median of n elements in \Theta(n) time so we're able to deterministically select as our pivot the median element.

This gives deterministic \Theta(n log n).

As mentioned elsewhere this algorithm has a fairly large constant factor and is not used in practice.

[ Parent | on HN ]