Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms

Question

In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity.

In practice, what is needed is an algorithm that would work fast on a finite (although possibly very large) number of instances.

An algorithm which works well in practice on the finite number of instances that we are interested in doesn't need to have good asymptotic complexity (good performance on a finite number of instances doesn't imply anything regarding the asymptotic complexity). Similarly, an algorithm with good asymptotic complexity may not work well in practice on the finite number of instances that we are interested in (e.g. because of large constants).

Why do we use asymptotic complexity? How do these asymptotic analysis related to design of algorithms in practice?

Answer 1

The interesting question is: what is the alternative? The only other method I know is testing/benchmarking. We program the algorithms, let them run on (a representative sample of) the finite input set and compare the results. There are a couple of problems with that.

• The results are not general in terms of machines. Run your benchmark on another computer and you get different results for sure, quantitatively, and maybe even qualitatively.
• The results are not general in terms of programming languages. Different languages may cause very different results.
• The results are not general in terms of implementation details. You literally compare programs, not algorithms; small changes in the implementation can cause huge differences in performance.
• If the worst-case is rare, a random input sample may not contain a bad instance. That is fair if you are concerned with average case performance, but some environments require worst-case guarantees.
• In practice, input sets change. Typically, inputs become larger over time. If you don't to repeat your benchmark every six months (yes, some data grow that fast), your results are worthless soon¹.

That said, ignoring all kinds of effects and constants in the analysis is typical, but can be called lazy (with respect to practice). It serves to compare algorithmic ideas more than to pinpoint the performance of a given (even pseudocode) implementation. It is well known to the community that this is coarse and that a closer look is often necessary; for example, Quicksort is less efficient than Insertion sort for (very) small inputs. To be fair, more precise analysis is usually hard².

Another, a posteriori justification for the formal, abstract viewpoint is that on this level, things are often clearer. Thus, decades of theoretic study have brought forth a host of algorithmic ideas and data structures which are of use in practice. The theoretically optimal algorithm is not always the one you want to use in practice -- there are other considerations but performance to make; think Fibonacci heaps -- and this label may not even be unique. It is hard for a typical programmer concerned with optimising arithmetic expressions would come up with a new idea on this level (not to say it does not happen); she can (and should) perform those optimisations on the assimilated idea, though.

There are formal, theoretic tools to close the gap to practice to some extent. Examples are

• considering memory hierarchy (and other I/O),
• analysing the average case (where appropriate),
• analysing numbers of individual statements (instead of abstract cost measures) and
• determining constant factors.

For example, Knuth is known for literally counting the numbers of different statements (for a given implementation in a given model), allowing for precise comparison of algorithms. That approach is impossible on an abstract level, and hard to do in more complex models (think Java). See [4] for a modern example.

There will always be a gap between theory and practice. We are currently working on a tool³ with the goal to combine the best of both worlds to make sound predictions for both algorithmic costs and runtime (on average), but so far we have not been able to do away with scenarios where one algorithm has higher costs but smaller runtime (on some machines) than an equivalent one (although we can detect that, and support finding the reason).

I recommend for practictioners to use theory to filter the space of algorithms before running benchmarks:

if ( input size forever bounded? ) {
  benchmark available implementations, choose best
  schedule new benchmarks for when machine changes
}
else {
  benchmark implementations of all asymptotically good algorithms
  choose the best
  schedule new benchmarks for when machine changes or inputs grow significantly
}

---

1. There can be crazy changes in absolute and relative performance once the number of cache misses increases, which typically happens when inputs grow but the machine stays the same.
2. As in, leading researchers in the field are not able to do it.
3. Find the tool here. An example use has been published in Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn by S. Wild et al. (2012) [preprint]
4. Average Case Analysis of Java 7’s Dual Pivot Quicksort by S. Wild and M. Nebel (2012) -- [preprint]

Answer 2

As noted in Raphael's answer, exact computation of worst-case running time can be very difficult. Exact computation can also be unnecessary since the RAM model already introduces approximations. For example, do all operations really take equal time? Specific implementations (hardware, optimizations) might speed up an algorithm by constant factors. We want to understand how effective an algorithm is independent of these factors. This is a big motivation for the use of asymptotic analysis.

Answer 3

I assume that this question arises from teaching a course which includes asymptotic analysis. There are several possible answers as to why this material is taught in introductory classes:

• Asymptotic analysis is a mathematical abstraction which yields itself to analysis. As (arguably) mathematicians, we want to be able to analyze algorithms, and they only way to tame their complexity is using asymptotic analysis.

• Evaluating the asymptotic performance of an algorithm does point out some principles which are useful in practice: for example, concentrate on that part of the code which takes the majority of time, and discount any part of the code which takes an asymptotically negligible part of time.

• Some of the techniques of asymptotic analysis are useful. I'm referring here mainly to the so-called "master theorem", which in many circumstances is a good description of reality.

• There is also a historical reason: when people first started to analyze algorithms, they earnestly thought that asymptotic complexity reflects practical usage. However, eventually they were proved wrong. The same thing happened with P as the class of efficiently solvable problems, and NP as the class of intractable problems, both of which are misleading in practice.

Personally, I think that asymptotic analysis is a reasonable part of the curriculum. More questionable parts include formal language theory and complexity theory (anything that has to do with a Turing machine). Some people make the argument that while these subjects are not useful to the would-be programmer per se, they do instill in her a certain mind-thought which is necessary to be a good practician. Others argue that theory sometimes influences practice, and these rare cases are enough to justify teaching these rather arcane subjects to the general computer science audience. I would rather have them learn history or literature, or any other subject they are actually interested in; both are as relevant to their future job prospects, and more important for them as human beings.

Answer 4

how about a simple near-visceral illustrative example using one of the most ubiquitous algorithms/applications in CS, namely sorting? Bubblesort takes $O(n^2)$ both average and worst case time and quicksort about $O(n \log n)$ on average and only $O(n^2)$ "rarely" in worst case. a nice way to see the difference is to look at the side-by-side, synchronized animations of sorting random arrays & their performance. almost always the bubblesort will take "longer" and one will be left waiting for it to finish in comparison to quicksort.

now imagine that wait repeated in the code as many times as the code is called. how does one mathematically quantify/justify this apparent superiority of the quicksort algorithm? (ie is its name really justified or is it just a marketing slogan?) via asymptotic complexity measurements. one is left looking at the animations subjectively feeling that bubblesort is somehow a weaker algorithm and asymptotic complexity analysis can prove this quantitatively. but note that asymptotic complexity analysis is just one tool in the bag of tools to analyze algorithms and its not always the ultimate one.

and its worth looking at the side-by-side code also. bubblesort seems to be conceptually simpler and doesnt use recursion. quicksort is not as immediately comprehended esp the "median of 3" pivot principle. bubblesort might be implemented just in loops without a subroutine, whereas quicksort might typically have at least one subroutine. this shows the pattern that more code sophistication can sometimes improve the asymptotic complexity at the expense of code simplicity. sometimes there is an extreme tradoff similar to the concept of diminishing marginal returns (orig from economics) where very large amts of code complexity [requiring entire papers full of thms and proofs to justify] only buys very small improvements in asymptotic complexity. this shows up as an example esp with matrix multiplication and can even be graphed.