Justifying asymptotic worst-case analysis to scientists

Question

I've been working on on introducing some results from computational complexity into theoretical biology, especially evolution & ecology, with the goal of being interesting/useful to biologists. One of the biggest difficulties I've faced is in justifying the usefulness of asymptotic worst-case analysis for lower bounds. Are there any article length references that justify lower bounds and asymptotic worst-case analysis to a scientific audience?

I am really looking for a good reference that I can defer to in my writing instead of having to go through the justifications in the limited space I have available (since that is not the central point of the article). I am also aware of other kinds and paradigms of analysis, so I am not seeking a reference that says worst-case is the "best" analysis (since there are settings when it very much isn't), but that it isn't completeletely useless: it can still gives us theoretically useful insights into the behavior of actual algorithms on actual inputs. It is also important the writing is targeted at general scientists and not just engineers, mathematicians, or computer scientists.

As an example, Tim Roughgarden's essay introducing complexity theory to economists is on the right track for what I want. However, only sections 1 and 2 are relevant (the rest is too economics specific) and the intended audience is a bit more comfortable with theorem-lemma-proof thinking than most scientists^[1].

---

Details

In the context of adaptive dynamics in evolution, I've met two specific types of resistance from theoretical biologists:

[A] "Why should I care about behavior for arbitrary $n$? I already know that the genome has $n = 3*10^9$ base pairs (or maybe $n = 2*10^4$ genes) and no more."

This is relatively easy to brush-off with the the argument of "we can imagine waiting for $10^9$ seconds, but not $2^{10^9}$". But, a more intricate argument might say that "sure, you say you care about only a specific $n$, but your theories never use this fact, they just use that it is large but finite, and it is your theory that we are studying with asymptotic analysis".

[B] "But you only showed that this is hard by building this specific landscape with these gadgets. Why should I care about this instead of the average?"

This is a more difficult critique to address, because a lot of the tools people commonly use in this field are coming from statistical physics where it is often safe to assume a uniform (or other specific simple) distribution. But biology is "physics with history" and almost everything isn't at equilibrium or 'typical', and empirical knowledge is insufficient to justify assumptions about distributions over input. In other words, I want an argument similar to that used against uniform distribution average-case analysis in software engineering: "we model the algorithm, we can't construct a reasonable model of how the user will interact with the algorithm or what their distribuition of inputs will be; that is for psychologists or end users, not us." Except in this case, the science isn't at a position where the equivalent of 'psychologists or end users' exists to figure out the underlying distributions (or if that is even meaningful).

Notes and related questions

1. The link discusses cognitive sciences, but the mindset is similar in biology. If your browse through Evolution or Journal of Theoretical Biology, you will seldom see theorem-lemma-proof, and when you do it will typically be just a calculation instead of something like an existence proof or intricate construction.
2. Paradigms for complexity analysis of algorithms
3. Other kinds of running time analysis besides worst-case, average-case, etc?
4. Ecology and evolution through the algorithmic lens
5. Why economists should care about computational complexity

Answer 1

My personal (and biased) take is that asymptotic worst-case analysis is a historical stepping stone to more practically useful kinds of analysis. It therefore seems hard to justify to practitioners.

Proving bounds for the worst case is often easier than proving bounds for even "nice" definitions of average case. Asymptotic analysis is also often much easier than proving reasonably tight bounds. Worst-case asymptotic analysis is therefore a great place to start.

The work of Daniel Spielman and Shanghua Teng on smoothed analysis of Simplex seems to me a harbinger of what can happen when we start to gain a better understanding of the shape of a problem: tackling the worst-case first enables a more nuanced understanding to be developed. Further, as Aaron Roth suggested in the comments, if the "usual" behaviour of a system is significantly different from its worst case, then the system is not yet completely specified and more work is needed to improve the model. So going beyond worst-case generally seems important as a long-term goal.

As far as asymptotic analysis is concerned, it usually serves to keep a long and messy proof clear of distracting details. Unfortunately there currently does not seem to be a way to reward the tedious work of filling in the details to obtain the actual constants, so that seldom seems to get done. (Page limits also work against this.) Careful analysis of the details of an asymptotic bound has led to actual algorithms, with good bounds on the constants, so I personally would like to see more of this kind of work. Perhaps if more proofs were formalised using proof assistant systems, then the constants could be estimated with less additional effort. (Or bounds on the constants, along the lines of Gowers' bound for the Szemerédi Regularity Lemma, might become more routine.) There are also ways to prove lower bounds that are free of constants, by using more explicit machine models (such as deterministic finite-state automata). However, such (near-)exact lower bounds for more general models of computation may require a lot of work, or be out of reach altogether. This seems to have been pursued in ~1958–73 during the first heyday of automata theory, but as far as I can tell has since largely been left alone.

In short: in future, I think we'll see worst-case analysis as just a first step, and I hope we'll see expressions like $O$^*$(n^k)$ with galactic hidden constants as just the first step. I find it difficult to justify the current focus on worst-case asymptotic analysis to practitioners, but perhaps it is useful to see this as the beginning steps of a longer journey.

Answer 2

Lower bounds and worst-case analysis don't usually go together. You don't say an algorithm will take at least exponential time in the worst case, therefore it's bad. You say it can take at most linear time in the worst case, and therefore is good. The former is only useful if you are going to run your algorithm on all possible inputs, and not merely an average input.

If you want to use lower bounds to demonstrate badness, then you want a best-case analysis or an average-case analysis. You can simplify things by relying on @PeterShor's point that worst and average are often very similar, and give a laundry list of algorithms for which this is true. (Ex: all the classic sorts besides quicksort.)

As for demonstrating that asymptotics matter when compared to constant inputs and constant factors, my favorite article on the topic is Jon Bentley's "Programming pearls: algorithm design techniques". He presents four different solutions to a simple array problem, and demonstrates how the linear approach annihilates the cubic one. He calls his table "The Tyranny of Asymptotics", after the term used by physicists for the intractability of the rocket equation. I use this example to motivate the search for better algorithms to pre-college students.

Will a non-computer scientist read through an article that contains code, and know to skip over the low-level details to get the big picture? I don't know. Perhaps there's a better presentation elsewhere. But I think this is a decent resource to cite.

And if they argue that they don't care about arbitrarily large n, have them run recursive un-memoized Fibonacci on 3 * 10⁹ base pairs, and tell them it's O(1) since the size of the DNA sequence is fixed. ;)

Answer 3

much agreed this an important topic to survey/cover but it seems not to have been much yet. a few refs of varying style/coverage/audience/ formality not exactly as requested but somewhat close (best seen online so far on medium search, hope to hear further of any better ones; more notes below):

• The complexity of algorithms Atkinson (alas only a single ref to biology in the paper, but may suffice on more general science/engineering terms)

  The modern theory of algorithms dates from the late 1960s when the method of asymptotic execution time measurement began to be used. It is argued that the subject has both an engineering and scientific wing. The engineering wing consists of well-understood design methodologies while the scientific wing is concerned with theoretical underpinnings. The key issues of both wings are surveyed. Finally some personal opinions on where the subject will go next are offered.

• Complexity and Algorithms J. Diaz. 100 slides. broad; one could excerpt relevant ones in particular.

• A Gentle Introduction to Algorithm Complexity Analysis Dionysis "dionyziz" Zindros

in other words is there a sort of introduction/survey/overview of the complexity theoretic lens in close combination/conjunction/companion with the advancing algorithmic lens in science, something like "Complexity theory for scientists, engineers, and researchers"?

there are good refs on the former "algorithmic lens" you have cited eg Papadimitriou but it does not seem a highly satisfactory ref by an expert in the field has been written on the latter "complexity lens"... yet (maybe some "elite" member of this site will consider that as their next book or paper project).

note also there are a lot of refs on relevance P vs NP outside of complexity theory & in other scientific fields that could be used somewhat for these purpose. will add them in comments if there is any interest.