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

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 3

There are two serious reasons to use asymptotic analysis of running times:

• to abstract away unimportant details. In many applications where we need non-trivial algorithms, most of the time is spent on problem instances that require medium to large numbers of operations, and we are more interested in the general trend than the exact operation count. In these applications, behavior for small $n$ is uninteresting.

• to allow mathematical tractability. Cases such that it is possible to find exact expressions for the operation count are exceptional. Studying asymptotics opens more possibilities (like asymptotic approximations of complicated functions are handy).

And there are many others (like machine independence, meaningfulness, comparability...).

Answer 4

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 5

Because asymptotics are "simple" (well, simpler than doing the exact analysis for finite cases, anyway).

Compare e.g. the encyclopaedic "The Art of Computer Programming" by Knuth, which does detailed analysis of all important algorithms (and many not-so-important ones) with the rule-of-thumb analysis that is often enough to get an asymptotic estimate (or just a bound), as practiced in most "algorithms" books.

You are certainly right. If the problem is important enough, a Knuth style (or perhaps a bit less detailed) analysis may well be warranted. In many cases, a hint at the asymptotic complexity (perhaps average with dispersion) fitted to experimental data is enough. In most cases, to do a rough classification of competing algorithms, as a first weed-out round comparing asymptotics can be precise enough. And if there are no contenders, getting the bad news of the exact cost in minute detail is just masochism.

Answer 6

Here by asymptotic analysis I assume we mean the behavior of algorithm as the size of the input goes to infinity.

The reason we use asymptotic analysis is because it is useful in predicting the behavior of algorithms in practice. The predictions allow us to make decisions, e.g. when we have different algorithms for a problem which one should we use? (Being useful doesn't mean it is always correct.)

The same question can be asked about any simplified model of real world. Why we use simplified mathematical models of the real world?

Think about physics. The classical Newtonian physics is not as good as relativistic physics in predicting the real world. But it is a good enough model for building cars, skyscrapers, submarines, airplanes, bridges, etc. There are cases where it is not good enough, e.g. if we want to build a satellite or send a space probe to Pluto or predict the movement of massive celestial objects like stars and planets or very high speed objects like electrons. It is important to know what are the limits of a model.

1. It is typically a good enough approximation of the real world. In practice we see often that an algorithm with better asymptotic analysis works better in practice. It is seldom the case that an algorithm has better asymptotic behavior So if the inputs can be large enough then we can typically rely on asymptotic analysis as a first prediction of algorithms behavior. It is not so if we know the inputs are going to be small. Depending on the performance we want we may need to do a more careful analysis, e.g. if we have information about the distribution of the inputs the algorithm will be given we can do a more careful analysis to achieve the goals we have (e.g. fast on 99% of inputs). The point is as a first step asymptotic analysis is a good starting point. In practice we should also make performance tests but keep in mind that also has its own issues.

2. It is relatively simple to compute in practice. Typically we can compute at least good bounds on the asymptotic complexity of an algorithm. For simplicity let's assume that we have an algorithm $A$ that outperforms any other algorithm on every input. How can we know $A$ is better than others? We can do asymptotic analysis and see that $A$ has better asymptotic complexity. What none of them are better than the other in all inputs? Then it becomes more tricky and depends on what we care about. Do we care about large inputs or small inputs? If we care about large inputs then it is not common that an algorithm has better asymptotic complexity but behaves worst on large inputs that we care. If we care more about small inputs then asymptotic analysis might not be that useful. We should compare the running time of the algorithms on inputs we care. In practice, for complicated tasks with complicated requirements asymptotic analysis might not be as useful. For simple basic problems that algorithm textbooks cover it is quite useful.

In short asymptotic complexity is a relatively easy to compute approximation of actual complexity of algorithms for simple basic tasks (problems in a algorithms textbook). As we build more complicated programs the performance requirements change and become more complicated and asymptotic analysis may not be as useful.

---

It is good to compare the asymptotic analysis to other approaches for predicting the performance of algorithms and comparing them. One common approach is performance tests against random or benchmark inputs. It is common when computing the asymptotic complexity is difficult or unfeasible, e.g. when we are using heuristics as in say SAT solving. Another case is when the requirements are more complicated, e.g. when a program's performance depends on outside factors and our goal might be to have something that finishes under some fixed time limits (e.g. think about updating interface shown to a user) on 99% of the inputs.

But keep in mind that performance analysis also has it's issues. It does not provide mathematical grantees on the performance on less we actually run the performance test on all inputs that will be given to the algorithm (often computationally infeasbile) (and it is often not possible to decide some inputs will never be given). If we test on against a random sample or a benchmark we are implicitly assuming some regularity about the performance of the algorithms, i.e. the algorithm will perform similarly on other inputs that were not part of the performance test.

The second issue with performance tests is that they depend on the test environment. I.e. the performance of a program is not determined by the inputs alone but outside factors (e.g. machine type, operation system, efficiency of coded algorithm, utilization of the CPU, memory access times, etc.) some of which might vary between different runs of the test on the same machine. Again here we are assuming that the particular environments that performance test are carried out are similar to the actual environment unless we do the performance tests on all environments that we may run the program on (and how can we predict what machines someone might run a sorting algorithm on in 10 years?).

Compare these to computing the asymptotic running time of say MergeSort ($\Theta(n \lg n)$) and comparing it with the running time of say SelectionSort ($\Theta(n^2)$) or BinarySerch ($\Theta(\lg n)$) with LinearSearch ($O(n)$).

Answer 7

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.