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

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?

-

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]
-
Arguably, the pure act of studying the theory of algorithms will sharpen your eye and train your abstraction-brain for algorithms, giving you another tool for evaluating code in every-day programming. Abstract away from the code, evaluate the principle, improve it and translate back to code. Example: "Ah, I see, you want to program a dictionary. But you essentially program lists; why not try trees?" –  Raphael Sep 13 '12 at 8:37
The limits of asymptotic analysis become obvious once you dig deeper; Quicksort is a prominent example. –  Raphael Nov 5 '14 at 15:19

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.

-
Thanks Yuval. The motivation is mainly interested in is how to explain to students the usefulness of asymptotic analysis and its relevance to the practice of designing and using algorithms in real applications (where most of the times it is clear that we are only interested in a finite though possibly very large number of instances), not justifying the curriculum. –  Kaveh Sep 14 '12 at 15:16
I am confused by your premise. You seem to assume the target group are both mathematicians and aspiring programmers, which is a weird combination and neither characterises computer scientists. (Also, I don't share your view on formal languages, but that's another topic.) –  Raphael Sep 15 '12 at 14:21
On the contrary, I assume that the target group is aspiring programmers. However, much of the curriculum is there for the sake of theoretical computer scientists. Of course, these two groups have conflicting needs. Since most of the undergraduate are would-be programmers, I think that the curriculum should be geared toward them, but some academics disagree. Perhaps they want to teach the future professors. Maybe you can explain their point of view. –  Yuval Filmus Sep 16 '12 at 18:24
@YuvalFilmus I have often explained that I do not believe that CS = TCS + Programming. If you teach a CS course (at a university) and most of your students want to be programmers, something is broken (imho). I would argue that any computer scientist can profit from solid education in algorithmics, formal languages and even some complexity theory (and many other things, such as how compilers and CPUs work). –  Raphael Sep 17 '12 at 17:38

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.

-

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.

-
There is lots of territory between "looking at animations" and formal analysis, such as extensive runtime benchmarks. They are actually a valid area of their own, as we don't have theory to explain all the stuff that influences runtimes. –  Raphael Sep 23 '12 at 21:23
@raphael you covered benchmarking in your answer; its a good answer. but note that animation/visualization can be closely related to benchmarking. actually there is plenty of explanation of what influences runtimes [covered in other answers] but to some degree its "noise" and asymptotic complexity "smooths/averages out the noise". thats another exercise to see how it actually does that. –  vzn Sep 24 '12 at 2:01
Animations don't filter out noise, though. Plus, the human eye is easily tricked, and it is just not feasible to watch animations for a reasonable-sized sample of reasonably sized lists (say, 1000 lists for sizes in the millions to benchmark sorting algorithms) and decide which was algorithm was faster (on the average). –  Raphael Sep 24 '12 at 5:38
the bubblesort vs quicksort example is intended to show the need/superiority for asymptotic analysis over benchmarking in some obvious cases. you can see the dramatic difference even for low values of $n$_. its intended as a "throwaway" or "demonstration" example— the viewer watches it once for low $n$ to see the utility of asymptotic analysis over benchmarking. plz remember the original question was about the need/importance/justification for _asymptotic analysis in algorithm analysis/dev. –  vzn Sep 24 '12 at 14:49
as for "smoothing out noise" see eg this graph. the pt is that you can take random inputs of size $n$, benchmark, and you will get "noisy" lines, and the asymptotic analysis gives the underlying mathematical "shape" of that line eg quadratic etc. –  vzn Sep 24 '12 at 15:34