O-notation considered harmful (use Analytic Combinatorics instead)
jng.imagine27.com
jng.imagine27.com
With minor tweaks to the selection of partitions, quick sort can be made O(n lg n). Specifically, if combined with linear time median finding, we can pick perfect partitions every time. (Of course, this algorithm is painfully slow in practice).
All this said, the idea of analytic combinatorics is interesting for a deeper understanding of algorithm performance. It quantifies behavior that good engineers understand is swept under the rug by Big-O notation.
Of course, if you really want good performance, you'll have to understand the algorithm beyond just it's combinatorial properties -- caching locality and coherence, branch mispredictions, function call-overhead etc. play an enormous role when it comes time to really make code fast.
To write fast code, you need the whole picture.
I have found way too many implementations in the wild, with various optimizations that STILL had an O(n^2) worse case, one that was actually triggered by real data.
> With minor tweaks to the selection of partitions, quick sort can be made O(n lg n). Specifically, if combined with linear time median finding, we can pick perfect partitions every time. (Of course, this algorithm is painfully slow in practice).
You are mostly contradicting yourself here. It is painfully slow in practice, therefore, no one does linear time median finding; therefore, partitions aren't equal sized, and the O(n lg n) guarantee CANNOT be made.
Have you ever seen a widely used quicksort implementation that actually has an O(n lg n) guarantee? I haven't. Closest I've seen is median-of-five-random-elements, which probabilistically is excellent, but is STILL not an O(n lg n) - if you have an adversary, and they build something like http://www.cs.dartmouth.edu/~doug/aqsort.c adjusted to your algorithm, you'll get a O(n^2).
Also, it is quite surprising how many quicksort implementations out there will do O(n^2) if they get a vector of ALL EQUAL VALUES. I have seen that happen in practice (including the Java standard library at the time I tested it), and I haven't seen one text book mention that the partitions should be (all < pivot) (all == pivot) (all > pivot), which is the only practical way to avoid it.
Here in the real world we don't have time to read a 800+ pages book on a subject promising to bring marginal productivity benefits. Me, I'd better read some fiction instead. It's so much better for your soul than any CS topic.
Most engineers I know would still argue that Merge Sort is a better solution and apparently Robert has had the same argumentative response even though he is an expert in the field. In the lecture he kindly says the following : “… Such people usually don’t program much and shouldn’t be recommending what practitioners do”.
As far as the practical utility of the techniques, for analyzing time, O-notation is clearly much better. Analyzing the exact number of steps taken is in most cases impossible, even with the powerful tools of analytic combinatorics. Analyzing the asymptotic time complexity is in comparison trivial. Even if you do manage to stumble on a case where it's possible to determine the exact number of steps, that still doesn't tell you anything about the constant factors involved in the algorithms, since you just have the number of steps for some definition of a step (those objecting that you could determine exactly how many CPU cycles an algorithm will take are living in the past -- with modern processors this is no longer feasible at all). The only thing that an exact step count can get you is non-leading terms that the O-notation hides. For example an algorithm might be O(n^2) when in fact the number of steps is n^2 + n. Knowing that extra +n is (almost) never of any practical importance, especially given that we're counting steps not time in seconds.
Don't get me wrong, analytic combinatorics is a beautiful subject and may even come in handy in some practical cases, but this post is vastly over-hyping it. By the way, even if you do want to count combinatorial structures exactly, instead of going the analytic combinatorics route in practice it often makes more sense to just define the exact count recursively and memoize. You don't get a closed form solution this way, but it is much quicker to do and can handle far more cases.
And I certainly wouldn't want to use a database with O(n) lookup or worse.
> O(n^2) means very slow very quickly.
You mean Theta(n^2) :-)
This gives deterministic \Theta(n log n).
As mentioned elsewhere this algorithm has a fairly large constant factor and is not used in practice.
Also, I never seen anyone claim that quick-sort is O(n^2). Usually it's considered only the average case, where it's also O(n log n). This is where I believe Analytic Combinatronics should come in: if you want to compare two algorithms with the same order of growth on the average case. Otherwise, I think it's better to use big-O (analytic combinatronics to compare linear vs. exponential growth algorithms seems a little bit of an "overkill").
The problem with "average case" analysis is that you must give your assumptions; Without precisely stating your assumptions, "average case" is useless.
Also, Big-O notation can primarily be used to see how algorithms scale with larger datasets. Not to see which algorithm is faster. (Although in a lot of cases, the better O-notation algorithm is also the faster one.)
If you have very performance critical code you probably have some sort of range of inputs in mind. In which case it's more practical to just do benchmarking and statistical based evaluation.
What's wrong with adding the word "is" between "X" and "considered"?
Who is doing the considering?
What is X harmful towards?
Can anyone explain why this is a thing?
http://en.wikipedia.org/wiki/Considered_harmful
Plus it's a quick way to write a pithy link-bait title (not commenting on the OP, but in general)
edit Actually according to Wikipedia Dijkstra's original title was different, and Niklaus Wirth changed it. I didn't know that, funny little bit of history.
Big-O applies to a hell of a lot more than just sorting algorithms, and no language lets you ignore the varying degrees of complexity that come from the choices you make.
Good developers consider Big-O implications all the time, without explicitly thinking about it. They don't ignore it.
We actually test incoming staff to make sure they are aware of complexity by giving them programming tasks that they can hang themselves with by using the wrong data structures or algorithms.
O(n) vs O(n^2) is not a small efficiency for non-trivial data sets. This is the point that was being made. Many people forget that the quote hinges on the word "small" and then use that as an excuse to disengage their brain when it comes to basic things.
Taking a quote, out of context really, and using it everywhere as some sort of justification, nay, an unthinking reflex, is, indeed, using it as a crutch.
Is there really any good reason not to focus optimization on areas it will make a difference, and guide it with actual profiling results?
And chosing the correct data structure comes down to understanding the performances (using Big-O / best-worst-average or Analytic Combinatorics) of the operations you're going to perform and the algorithms you're going to use on these data structures.
It really sucks to have to refactor a codebase because some coder thoughts that lists would have been great there when actually a bi-dir map was what was needed (and vice-versa).
If you have code which does a database query, parses some result and then generates HTML based on that; this is an algorithm. If your Javascript walks the DOM finding elements then that is an algorithm.
These things all have associated computational costs which will scale depending on the input size.
O notation specifies the asymptotic behavior of (mathematical) functions. e.g. sqrt(n) = O(n/log(n))
In order to use O notation to describe the performance of an algorithm, one must specify 1. What is being measured and 2. What is the class of inputs.