O-notation considered harmful (use Analytic Combinatorics instead)

http://jng.imagine27.com/index.php/2013-02-10-121226_analytic-combinatorics-is-better-o-nation-considered-harmful.html

by jgrant27 • 13 years ago

37 38 13 years ago

jng.imagine27.com

patrickg• 13 years ago

Isn't that why we look at best/average _and_ worst case? Not only the worst case alone?

schabernakk• 13 years ago

My thought exactly. Quicksort for example has an average case of n log n, just like mergesort.

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.)

tensor• 13 years ago

It seems that analytic combinatorics (what is advocated instead of big-Oh) is the modern study of things like average case analysis. That said, it seems like bad advice to advocate ignorance of the worst case. Both average and worst cases should be considered.

freework2• 13 years ago

Most of the time, if you're thinking about big-O, you're practicing pre-mature optimization. Just write the code using your language's sort() function. If by profiling you determine the call to sort() is a bottleneck, then AND ONLY THEN should you consider analyzing the big-o implications of the different sort algorithms.

lucian19002• 13 years ago

However, it is often important to keep in mind how a particular functionality will scale. Complexity is an excellent way to gauge that.

thirsteh• 13 years ago

I strongly disagree. Good developers have a sort of Big-O intuition at the back of their minds that automatically tells them that the nested for loop they're writing to find a string in an array, and using an array in the first place, might not be the right approach.

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.

meaty• 13 years ago

I think this is the most elegant set of reasons.

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.

dinkumthinkum2• 13 years ago

No, that's not true. That may be true if your whole world is making CRUD apps but there is a whole world out there. People use the phrase "pre-mature optimization" as a crunch to not understand how computers work.

paulgb• 13 years ago

Exactly. If you're building a todo list maybe you can ignore complexity, but if you're working on a data pipeline and you ignore (at least an intuitive sense of) O-notation, it will bit you in the ass.

10098• 13 years ago

This. I can't comprehend it when people use sort() to find the min/max element instead of a linear scan. And yes, I've seen it happen.

philhippus• 13 years ago

So Donald Knuth was trying to get out of understanding computers, got it.

slurgfest• 13 years ago

People also use the phrase "premature optimization" to make a perfectly accurate observation about eager, costly optimizations which may be obviated by changes or have no meaningful relationship to any business need.

Is there really any good reason not to focus optimization on areas it will make a difference, and guide it with actual profiling results?

freework2• 13 years ago

99% of everything is CRUD

martinced• 13 years ago

Writing correct code is about chosing correct data structures for the problem at hand as much as "coding".

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).

mjcohen• 13 years ago

Algorithms + Data Structures -> Programs.

guard-of-terra2• 13 years ago

It's not only sort. Any loop with function calls inside can be a source of runaway complexity.

jiggy20112• 13 years ago

It seems impossible to talk about Big O without comparing sorting algorithms. I guess this is because every college course on the planet compares sorting algorithms for half the semester.

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.

revelation• 13 years 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• 13 years ago

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) :-)

Derander2• 13 years ago

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.

JD557• 13 years ago

I can't say I completly agree with this. Even though big-O notation is far from perfect, I assume analytic combinatronics has its problems as well: since it's based on the scientific method, it should have some errors (although I have not read about it, so I might be wrong).

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").

beagle32• 13 years ago

Every ref to quicksort worth its salt mentions that it is O(n log n) average case, and O(n^2) worst case.

The problem with "average case" analysis is that you must give your assumptions; Without precisely stating your assumptions, "average case" is useless.

gnosis• 13 years ago

Cached version:

http://jng.imagine27.com.nyud.net/index.php/2013-02-10-12122...

guard-of-terra2• 13 years ago

They can't be serious if they don't provide a cheat sheet - a page worth of notations for common algorithms demonstrating how to use the thing and how it's superior.

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.

stevvooe• 13 years ago

Not to mention the condescending attitude:

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”.

rcoh• 13 years ago

I became irritated when quick sort was claimed be O(n^2). Not only is that not true in practice, it's just wrong for all but the simplest implementations of the algorithm.

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.

beagle32• 13 years ago

> Not only is that not true in practice, it's just wrong for all but the simplest implementations of the algorithm.

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.

danek• 13 years ago

What is the origin of these articles that take the form "X Considered Harmful"?

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?

spacemanaki• 13 years ago

Its origins are in an essay by Dijkstra from 1968 called "Go To Statement Considered Harmful"

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.

shadowfiend• 13 years ago

This is a thing because it is an allusion to Edsger Dijkstra's letter “Go To Statement Considered Harmful”. See more at http://en.wikipedia.org/wiki/Considered_harmful . Evidently it predates that letter, but its pervasion in computing blog posts and such is probably due to the relation to Dijkstra's article/letter.

jiggy20112• 13 years ago

IMO, Understanding Big O helps you avoid doing stupid stuff like O(n!) where the problem can grow faster than your ability to purchase hardware to keep up. But you probably know when you are writing code like this intuitively.

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.

amit_m• 13 years ago

I don't get this post.

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.

rck• 13 years ago

Using complex analysis to study generating functions that describe time complexity is definitely interesting, and there are some cases where using generating functions can make a complicated analysis a bit easier to deal with, but I don't see any reason to think that analytic combinatorics is more practical on a day-to-day basis than big-O notation. Analytic combinatorics is much closer in spirit to the techniques that Knuth uses to analyze performance in The Art of Computer Programming, and I don't know many programmers who prefer Knuth's style of analysis to big-O.

jules• 13 years ago

Quick sort being O(n^2) and merge sort O(n log n) has nothing to do with O-notation (asymptotic analysis) vs analytic combinatorics (exact step counting). With analytic combinatorics you may get the exact number of steps the algorithm takes yes, but the leading term in quicksort's step count would still be n^2 and the leading term for mergesort's step count would still be n log n. The problem this post is about has everything to do with worst case vs average case. You can analyze average case and worst case both asymptotically and exactly.

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.

tbirdz• 13 years ago

Just in case you missed it, the book is free off the author's website: http://algo.inria.fr/flajolet/Publications/book.pdf

O-notation considered harmful (use Analytic Combinatorics instead)

Related Stories