3 ms·
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 framew
by revelation 14y ago
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.
- praptak 14y agoSame 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) :-)
- Derander 14y agoIf 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.