Justifying asymptotic worst-case analysis to scientists I've been working on on introducing some results from computational complexity into theoretical biology, especially evolution &amp; 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 &quot;best&quot; 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] &quot;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.&quot;
This is relatively easy to brush-off with the the argument of &quot;we can imagine waiting for $10^9$ seconds, but not $2^{10^9}$&quot;. But, a more intricate argument might say that &quot;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&quot;.
[B] &quot;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?&quot;
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 &quot;physics with history&quot; 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: &quot;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.&quot; 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

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.
Paradigms for complexity analysis of algorithms
Other kinds of running time analysis besides worst-case, average-case, etc?
Ecology and evolution through the algorithmic lens
Why economists should care about computational complexity
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$&#42;$(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.