O-notation considered harmful (use Analytic Combinatorics instead)

Re:O-notation considered harmful (use Analytic Combinatorics... by revelation on Sunday February 10, 2013 @04:28PM (#5197984)

Of course O-notation is mostly misguided, but then there are places where it comes back to bite you. Remember that DoS that worked on basically every web framework out there because everything is a clever hash-table nowadays? O(n^2) means very slow very quickly.

And I certainly wouldn't want to use a database with O(n) lookup or worse.

[ Parent | on HN ]

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 ]