<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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$<sup>&#42;</sup>$(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.</p>

CC BY-SA 3.0
2014-01-31T01:05:21.047Z
I don't share your enthusiasm for ditching asymptotics in favor of precise bounds with definite constants. Asymptotics may be imprecise -- but they're usefully imprecise. They abstract over implementation differences for the same machine model. E.g., a sorting algorithm that was quadratic on 1950s hardware will still be quadratic on today's hardware. Furthermore, asymptotic formulas compose nicely. Linears and polynomials are closed under composition, for instance. (Note that arguing for better bounds on the average case compared to worst case is orthogonal from arguing against asymptotics.)
brandjon
CC BY-SA 3.0
2014-01-31T01:13:45.947Z
You are right in general, but there is a big difference between a small constant and one that is a non-elementary function of a relevant parameter.
András Salamon
CC BY-SA 3.0
2014-01-31T18:13:06.420Z
I like this answer overall, but I agree with @brandjon that hiding constants is crucial. For me, the reason TCS is useful in biology is because it needs to make much fewer assumptions about micro dynamics than physics. However, if you don't make assumptions about the micro dynamics (I.e. the exact specification of the model of computation) then you can't get the constant factors out. The other useful feature of TCS is rigorous qualitative dichotomies (something that is easier to compare to the more qualitative observations in bio), usually to get these you also have to ditch constants.
Artem Kaznatcheev
CC BY-SA 3.0
2014-02-01T02:44:15.290Z
@Erhart it required a pretty strong assumption about the microdynamics: that only comparisons are allowed. In an evolutionary biology setting, an assumption of that strength would be saying that only adaptive walks on point-mutations in asexual organisms are allowed (in this case we can also prove lower bounds where we know the constants).
Artem Kaznatcheev
CC BY-SA 3.0
2014-02-03T02:42:31.563Z
As a side note, there are examples where worst-case analysis makes sense. For example, when you develop a library of general-purpose subroutines and do not know in what application domains they will be useful: you cannot possibly anticipate all cases of when and why someone will want to compute a minimum cost bipartite matching, for example. Adversarial settings, such as cryptography, are even more clear cut (however, in crypto you'd really like to know the constants when it comes to security parameters).
Sasho Nikolov
CC BY-SA 3.0
2014-01-30T20:59:31.417Z
2014-01-30T20:59:31.417Z
András Salamon
<p>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.</p>

<p>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.)</p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2014-01-28T17:58:19.117Z
I like the fibonacci example :)
Suresh Venkat
CC BY-SA 3.0
2014-01-30T21:15:38.160Z
Re: your first paragraph: actually, that's almost exactly what a lot of complexity theory does. If a problem is EXP-complete, that means it requires exponential time on worst-case inputs. This is generally taken as an indication of its overall difficulty (which, to be fair, in practice is often not so bad as a  general indicator). This is the de facto standard, called an "infinitely-often" or i.o. lower bound; getting average-case or almost-everywhere lower bounds (that is, for all but finitely many inputs) is a goal sometimes pursued, but often far out of reach compared to i.o. lower bounds.
Joshua Grochow
CC BY-SA 3.0
2014-01-30T21:28:18.240Z
Let me point out that not only can you give a laundry list of algorithms for which worst-case and average-case analysis are the same, but you can also give numerous examples where they are very different (the simplex algorithm just being the most famous of these). You really need to argue somehow that they are the same for your particular application; experimental testing is a good way to do this.
Peter Shor 
CC BY-SA 3.0
2014-01-31T00:56:47.973Z
@JoshuaGrochow Fair enough. How about we revise the statement as follows: Lower bounds on worst-cases are important when you want to demonstrate the absence of a mathematical guarantee of non-horribleness. ;)
brandjon
CC BY-SA 3.0
2014-01-28T17:01:06.090Z
2014-01-28T17:01:06.090Z
brandjon
<p>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/ <em>formality</em> not <em>exactly</em> as requested but somewhat close (best seen online so far on medium search, hope to hear further of any better ones; more notes below):</p>
<ul>
<li><p><a href="http://www.cs.otago.ac.nz/staffpriv/mike/Papers/Wand/Wand.pdf" rel="nofollow noreferrer">The complexity of algorithms</a> Atkinson (alas only a single ref to biology in the paper, but may suffice on more general science/engineering terms)</p>
<blockquote>
<p>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 scientiﬁc wing.
The engineering wing consists of well-understood design methodologies
while the scientiﬁc 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 oﬀered.</p>
</blockquote>
</li>
<li><p><a href="http://www.cs.uu.nl/groups/AD/compl-diaz.pdf" rel="nofollow noreferrer">Complexity and Algorithms</a> J. Diaz. 100 slides. broad; one could excerpt relevant ones in particular.</p>
</li>
<li><p><a href="http://discrete.gr/complexity/" rel="nofollow noreferrer">A Gentle Introduction to Algorithm Complexity Analysis</a> Dionysis &quot;dionyziz&quot; Zindros</p>
</li>
</ul>
<p>in other words is there a sort of introduction/survey/overview of the <em>complexity theoretic</em> lens in close combination/conjunction/companion with the advancing <em>algorithmic lens</em> in science, something like <em>&quot;Complexity theory for scientists, engineers, and researchers&quot;</em>?</p>
<p>there are good refs on the former &quot;algorithmic lens&quot; you have cited eg <a href="http://lazowska.cs.washington.edu/fcrc/Christos.FCRC.pdf" rel="nofollow noreferrer">Papadimitriou</a> but it does not seem a highly satisfactory ref by an expert in the field has been written on the latter &quot;complexity lens&quot;... <em>yet</em> (maybe some <em>&quot;elite&quot;</em> member of this site will consider that as their next book or paper project).</p>
<p>note also there are a lot of refs on relevance P vs NP outside of complexity theory &amp; in other scientific fields that could be used somewhat for these purpose. will add them in comments if there is any interest.</p>

CC BY-SA 3.0
2014-01-29T20:16:53.723Z
I don't think this really answers the question.
Huck Bennett
CC BY-SA 3.0
2014-01-29T20:18:55.230Z
uh huh, did you look at _any_ of the refs? part my answer is that there is not _(yet)_ any ideal/perfect answer :|
vzn
CC BY-SA 3.0
2014-01-29T20:21:45.243Z
They seem to define asymptotic and worst case analysis rather than focusing on justifying it, but maybe I missed something?
Huck Bennett
CC BY-SA 3.0
2014-01-29T21:35:23.137Z
seems to me all the refs have substantial-to-strong elements justifying the use of complexity theory (analysis) of algorithms in general outside TCS to scientists, engrs, researchers etc... wasnt that clear looking at them? (concede already it would indeed be better if something was written by a leader in the field...have not found that)... re asymptotic vs worst case, is the question really focused on that? _cant tell_ ... maybe researchers outside the field are unlikely to consider this distinction as crucial/pivotal as those inside of it ... & likely too specialized to find that ref ...
vzn
CC BY-SA 3.0
2014-01-30T02:59:34.110Z
Actually, I think researchers outside TCS could easily dismiss worst-case as "artificially constructed examples that would never occur in practice" and would be (without strong convincing otherwise) much more interested in average-case (despite the fact that it's not clear that the average-case is that much closer to real-world instances).
Joshua Grochow
CC BY-SA 3.0
2014-01-30T03:35:27.503Z
seems to me for many algorithms & data that arise in practice (eg random instances of NP complete problems), average and worst case performance are related, so practitioners need to understand basic concepts of TCS (such as "easy" vs "hard" instances and "easy" vs "hard" problems and "inefficient" vs "efficient" algorithms & how these are scientifically quantified) but do not nec have to be so attentive to complexity-theoretic distinctions about performance that TCS researchers meticulously focus on. (and thought this pov is in line with the request in the original question, is it not?)
vzn
CC BY-SA 3.0
2014-01-31T16:27:57.837Z
@joshua more thinking on this, dont understand why TCS theorists would find it nec to _"justify"_ worst case analysis. the origins of this theory in [Big-O notation (Laundau functions)](http://en.wikipedia.org/wiki/Big_O_notation) are from earlier _mathematics_ & even number theory. it is _intrinsic_ to complexity theory, virtually a _fundamental theorem_ that algorithms have complexity that can be measured. also that concept can be used for other than algorithm speed measurement, eg population growth etc.; outside of that there are subtleties/nuances that deserve further attn...
vzn
CC BY-SA 3.0
2014-01-31T17:28:35.487Z
moreover if practitioners didnt care about _worst case_ they would be using _easier-implemented_ $O(n^2)$ _bubble sort_ instead of $O(n \log n)$ quicksort where the latter is harder to understand/implement.... are we sort of getting _wrapped around the axle here_ in this discussion....?
vzn
CC BY-SA 3.0
2014-01-31T22:51:26.603Z
@vzn: Asymptotic (e.g. big-Oh) and worst-case are somewhat orthogonal. One can do asymptotic worst-case analysis, asymptotic average-case analysis, or even asymptotic *easiest*-case analysis (though I admit the latter seems somewhat perverse). One could instead do *exact* worst-case analysis, or *exact* average-case analysis, and so on, though these would be much more model-dependent and less robust. Justifying the use of asymptotics (and hiding things like constant factors) is entirely distinct from justifying worst-case vs average-case or "real-"case (whatever the latter might mean...).
Joshua Grochow
CC BY-SA 3.0
2014-01-29T19:40:01.800Z
2014-01-29T20:11:27.837Z
2020-06-17T09:38:08.363Z
vzn
<p>I've been working on on introducing <a href="http://egtheory.wordpress.com/2013/08/31/evolutionary-equilibria/" rel="noreferrer">some results</a> from computational complexity into theoretical biology, especially <a href="https://cstheory.stackexchange.com/q/14103/1037">evolution &amp; ecology</a>, 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. <strong>Are there any article length references that justify lower bounds and asymptotic worst-case analysis to a scientific audience?</strong></p>
<p>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 <a href="https://cstheory.stackexchange.com/q/894/1037">other kinds</a> and <a href="https://cstheory.stackexchange.com/q/7203/1037">paradigms</a> of analysis, so <strong>I am <em>not</em> seeking a reference that says worst-case is the &quot;best&quot; analysis</strong> (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 <em>actual</em> algorithms on <em>actual</em> inputs. It is also important the <strong>writing is targeted at general scientists</strong> and not just engineers, mathematicians, or computer scientists.</p>
<p>As an example, <a href="http://theory.stanford.edu/%7Etim/papers/et.pdf" rel="noreferrer">Tim Roughgarden's essay introducing complexity theory to economists</a> 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 <a href="https://cogsci.stackexchange.com/a/4807/29">most scientists</a><sup>[1]</sup>.</p>
<hr />
<h3>Details</h3>
<p>In the context of <a href="http://egtheory.wordpress.com/2013/08/16/fitness-landscapes/" rel="noreferrer">adaptive dynamics in evolution</a>, I've met two specific types of resistance from theoretical biologists:</p>
<p>[A] &quot;Why should I care about behavior for arbitrary <span class="math-container">$n$</span>? I already know that the genome has <span class="math-container">$n = 3*10^9$</span> base pairs (or maybe <span class="math-container">$n = 2*10^4$</span> genes) and no more.&quot;</p>
<p>This is relatively easy to brush-off with the the argument of &quot;we can imagine waiting for <span class="math-container">$10^9$</span> seconds, but not <span class="math-container">$2^{10^9}$</span>&quot;. But, a more intricate argument might say that &quot;sure, you say you care about only a specific <span class="math-container">$n$</span>, 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;.</p>
<p>[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;</p>
<p>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 <a href="http://egtheory.wordpress.com/2013/08/18/empirical-epistasis/" rel="noreferrer">empirical knowledge is insufficient</a> 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).</p>
<h3>Notes and related questions</h3>
<ol>
<li>The link discusses cognitive sciences, but the mindset is similar in biology. If your browse through <em>Evolution</em> or <em>Journal of Theoretical Biology</em>, 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.</li>
<li><a href="https://cstheory.stackexchange.com/q/7203/1037">Paradigms for complexity analysis of algorithms</a></li>
<li><a href="https://cstheory.stackexchange.com/q/894/1037">Other kinds of running time analysis besides worst-case, average-case, etc?</a></li>
<li><a href="https://cstheory.stackexchange.com/q/14103/1037">Ecology and evolution through the algorithmic lens</a></li>
<li><a href="https://cstheory.stackexchange.com/q/17552/1037">Why economists should care about computational complexity</a></li>
</ol>

CC BY-SA 3.0
2014-01-25T23:15:24.190Z
Worst-case behavior is impossible to justify … the simplex algorithm has exponential worse-case behavior, and the only people who have ever cared are the theorists. What you need to argue is (a) the average-case asymptotic behavior is important; (b) the average-case asymptotic behavior and worst-case asymptotic behavior are quite often similar; (c) the worst-case asymptotic behavior is often much easier to calculate than the average-case asymptotic behavior (especially since nobody knows what the relevant probability distribution is).
Peter Shor 
CC BY-SA 3.0
2014-01-25T23:23:57.267Z
@PeterShor average-case becomes very weird for natural systems when we don't really give them inputs. For instance, if we are trying to argue that the [Arrow-Debrue model](http://en.wikipedia.org/wiki/Arrow%E2%80%93Debreu_model) is not the full story, we can say that using it (without further restrictions on the structure of markets considered) clashes with the popular assumption of "relatively quick" market equilibration. How can we possibly argue for a distribution over markets here? Aren't we just doing a philosophical analysis of if our assumptions fit? Or is such analysis of no interest?
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-25T23:26:14.470Z
@PeterShor any tips/advice on arguing part (b) in your recipe? Or is this completely problem/context specific?
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-26T00:22:57.480Z
As Peter says, it's very difficult to justify worst-case analysis. A much "easier" explanation is to demonstrate that an algorithm with good worst-case guarantees is in fact better in practice. A set of such cases is more compelling than any argument from principle.
Suresh Venkat
CC BY-SA 3.0
2014-01-26T00:27:17.200Z
@SureshVenkat but how do we do that when what we care about is lower bounds? In particular, my urge for using complexity arguments in fields like biology is specifically because we currently have no way to argue about certain microdynamics and thus no access to specific algorithms.
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-26T00:28:37.573Z
@Artem: I know a little bit about biology … it would really help me if you gave some specific examples of the kind of thing you are talking about.
Peter Shor 
CC BY-SA 3.0
2014-01-26T00:47:26.787Z
@PeterShor To shamelessly push [my own preprint](http://arxiv.org/abs/1308.5094): there the goal is to use _very_ simple TCS to point out that "being at a (local) fitness peak" is an unreasonable assumption and should not be so freely made, contributing to a discussion in biology spurred by the [recent results from the Lenski's LTEE](http://telliamedrevisited.wordpress.com/2013/12/08/what-weve-learned-about-evolution-from-the-ltee-number-2/). To avoid being too chatty, I'd be happy to continue [on this blog post](http://egtheory.wordpress.com/2013/08/31/evolutionary-equilibria/) or by email.
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-26T01:56:41.170Z
Asymptotics is already a problematic aspect. We all know the story about matrix multiplication algorithms (asymptotic upper bounds are meaningless in practice), and perhaps also the story about choosing parameters in cryptography (asymptotic lower bounds are meaningless in practice; exponential algorithms are sometimes feasible [DES]). If your analysis has actual constants then it is more convincing.
Yuval Filmus
CC BY-SA 3.0
2014-01-26T03:38:08.783Z
I agree with everything that's been said so far, but want to add one point about [B]. In some sense, your response should be: actually, we don't care about the worst-case or the average-case, because (as you say) biology is typically not at equilibrium. The issue is that no one has a good model that produces something which "looks like" the real-world case. This is the source of a lot of work on generative models of networks that "look like" real-world networks. As to why worst-case, I'd stick with Peter Shor's argument, *especially* (c) - often worst-case analysis is the best we can do.
Joshua Grochow
CC BY-SA 3.0
2014-01-26T03:46:21.403Z
If you think about computation as a game (i.e., war) between the input provider and the algorithm, then the worst case analysis is a standard military approach - you want to know how bad can it be. Secondly, and more importantly, worst case analysis does not allow you to be intellectually lazy and accept solutions that might be good to what you believe the world is (and not what the world is really is). Finally, and maybe most importantly, it provide a uniform way to compare algorithms in a hopefully meaningful way. In short, it is the worst approach, except for all the others.
Sariel Har-Peled
CC BY-SA 3.0
2014-01-26T12:24:29.190Z
@PeterShor your comment makes a good answer.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-26T14:04:43.700Z
@SarielHar-Peled I like the "does not allow you to be intellectually lazy" argument, but for lower bounds people can just argue "you are just picking this family of instances to prove your point, and is not a good description of how 'real' instances 'really' are", so it would have to be given more carefully to avoid this response.
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-26T14:12:13.593Z
@YuvalFilmus I agree that it is better to keep constants around, but sometimes (I would even say, oftentimes for lower-bounds) it is impossible. A classic example would be that additive constants are meaningless in Kolmogorov complexity. In my specific case, I am using TCS because it allow making minimal assumptions about underlying dynamics. i.e. I can't specify my model of computation (that would be assuming to much on the microdynamics) beyond saying it is 'reasonable' (for instance, doesn't grow resources super-polynomially) and that makes constants (and sometimes larger terms) meaningless
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-26T14:25:19.237Z
@JoshuaGrochow I agree very much. I actually use the unreasonableness of the worst-case results to argue that we need to think about a particular problem away from equilibrium. I also like (c) as a justification for worst-case analysis in TCS, but in biology I actually make a (c)-like argument against using the more common equilibrium analysis, and so my hands are a bit tied.
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-26T23:10:20.623Z
@SarielHar-Peled: +1 for "Worst-case analysis is the worst approach, except for all the others" :).
Joshua Grochow
CC BY-SA 3.0
2014-01-27T10:17:59.297Z
Worst case analysis is as useless as frequentist statistics. It answers a question no one has asked you (what is the worst possible scaling of your algorithm over all possible inputs and an unbounded input size) just as frequentist stats answers the question "What is the probability of the data given the model?" when you clearly want to know the probability of the model given the data (i.e. is he guilty?).  However both have turned out to be quite useful...
Simd
CC BY-SA 3.0
2014-01-28T21:59:07.863Z
I think a worst-case lower bound should be seen as putting the ball back in their court. You have shown that there is no algorithm that can solve their problem on all instances in a reasonable time frame. They may reasonably believe that their instances are easy -- but you have just shown that if this is so, it is a non-trivial fact. Their model is therefore incomplete unless they come up with an explanation for why this is so.
Aaron Roth
CC BY-SA 3.0
2014-01-28T22:01:53.467Z
(This is the approach that seems to work when talking to game theorists. It raises the question -- if markets truly equilibriate quickly -- what special property do real markets have that gets around worst case hardness? It is likely possible to define a plausible such property, and the lower bounds just suggest that doing so is an important research direction)
Aaron Roth
CC BY-SA 3.0
2014-01-28T23:32:23.277Z
@AaronRoth this is my thinking as well. Do you know a source outside of econ (or comp sci, or math) which expands on these ideas?
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-30T20:03:02.557Z
Aaron makes a great point.  However, I'm not sure arguments that work in the presence of markets, where there are incentives to seek out the extreme behaviours that maximize gains, apply also to biology.  Are the dynamics really comparable?
András Salamon
CC BY-SA 3.0
2014-01-30T21:40:05.493Z
Speed of light, $C$, is very important to them, see [Grace Hopper's lecture](http://www.youtube.com/watch?v=JEpsKnWZrJ8). If you give them a lower bound on a distributed algorithm every message passed is going to incur a lower bound of $C * distance$ no matter how big their research budget is.
Chad Brewbaker
CC BY-SA 3.0
2014-01-31T09:50:29.410Z
@PeterShor, For simplex worse case I do not think that we can compare it with usual algorithms, simplex can solve some NP-Complete problems in its worst case scenario,so that worst case probably is not bad (it's meaningful), take a look at this paper: http://arxiv.org/abs/1311.5935.
Saeed
CC BY-SA 3.0
2014-01-31T17:37:21.990Z
@Saeed: For simplex simply viewed as an algorithm for solving linear programs, I think you can compare it with the usual algorithms; simplex doesn't solve NP-complete problems unless you pick a particular instantiation of the simplex algorithm and start worrying about its inner workings.
Peter Shor 
CC BY-SA 3.0
2014-01-31T17:55:19.720Z
are you guys all overthinking this? worst case analysis is just a simple/basic _mathematical property_ of algorithms. it is a _fundamental conceptual starting/launching point_ for understanding more subtle nuances of performance such as how average case behaves (which is more based on _statistics_). worst case analysis focuses by nature on _extremes_. as for significance of average vs worst case how about the toy/universal model of [sorting algorithms](http://en.wikipedia.org/wiki/Best,_worst_and_average_case#Examples).... & comparing bubble sort vs quicksort etcetera....
vzn
CC BY-SA 3.0
2014-01-31T18:01:56.717Z
another field where there are good examples/"justification" is ***cryptography*** where the security of the algorithm ***hinges*** on the distinction. a supposed trap door function which is hard in worst case but easy in average case is ***worthless/insecure*** etc....
vzn
CC BY-SA 3.0
2014-01-31T18:04:46.753Z
@vzn thank you for the feedback, the interest is sciences that are not directly related to computing. Hence, cryptography is not relevant to the discussion.
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-31T18:06:53.360Z
@AndrásSalamon you make a great point about markets potentially 'seeking' worst case behaviour. However, it isn't obvious to me that this is irrelevant for biology. The key feature there is historicity, so even if we can't make an argument for seeking the worst-case, we also can't make an argument for average case.
Artem Kaznatcheev
CC BY-SA 3.0
2014-01-31T18:12:36.717Z
the [A]/[B] objections given by biologists listed in the question are interesting but seem almost to be maybe pushing against too much TCS _abstraction_ introduced into a field of more physical/concrete analysis.. and too much abstraction standing in way of applicability is indeed a legitimate complaint of practitioners to much of TCS research! it would be helpful if you could quote more at length the "objections" & fill out more context....
vzn
CC BY-SA 3.0
2014-02-01T00:13:26.760Z
@PeterShor, I think if you didn't look at my referenced paper, is not bad to look at it's introduction and some definitions and theorems without going in details. They prove that simplex implicitly solves np-complete problems, the definitions are somehow technical but in my humble opinion their argument is reasonable, that means we can classify algorithms in another point of view, in this classification simplex is an algorithm with some (magical) power (in its worst case scenario). What I want to say is that, it's not a good way to compare simplex with ordinary algorithms.
Saeed
CC BY-SA 3.0
2014-02-01T02:06:35.770Z
how about as a _"justification" (still on the highly questionable premise it_ needs _one), [goedel invented it in a letter to von neumann](http://rjlipton.wordpress.com/the-gdel-letter/) over ½-century ago?_
vzn
CC BY-SA 3.0
2014-02-07T16:45:53.287Z
ran across this similar question on [cs.se]: [Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms](http://cs.stackexchange.com/questions/3523/8)
vzn
<cc.complexity-theory><reference-request><big-picture><application-of-theory><worst-case>
Justifying asymptotic worst-case analysis to scientists
Artem Kaznatcheev
# Justifying asymptotic worst-case analysis to scientists

(Asked by: username_0 on 2014-01-25)

I've been working on on introducing [some results](http://egtheory.wordpress.com/2013/08/31/evolutionary-equilibria/) from computational complexity into theoretical biology, especially [evolution & ecology](https://cstheory.stackexchange.com/q/14103/1037), 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](https://cstheory.stackexchange.com/q/894/1037) and [paradigms](https://cstheory.stackexchange.com/q/7203/1037) 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](http://theory.stanford.edu/%7Etim/papers/et.pdf) 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](https://cogsci.stackexchange.com/a/4807/29)[1].

---

### Details

In the context of [adaptive dynamics in evolution](http://egtheory.wordpress.com/2013/08/16/fitness-landscapes/), 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](http://egtheory.wordpress.com/2013/08/18/empirical-epistasis/) 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](https://cstheory.stackexchange.com/q/7203/1037)
3. [Other kinds of running time analysis besides worst-case, average-case, etc?](https://cstheory.stackexchange.com/q/894/1037)
4. [Ecology and evolution through the algorithmic lens](https://cstheory.stackexchange.com/q/14103/1037)
5. [Why economists should care about computational complexity](https://cstheory.stackexchange.com/q/17552/1037)

**Tags:** cc.complexity-theory, reference-request, big-picture, application-of-theory, worst-case
> **Comments:**
> **username_1**: Worst-case behavior is impossible to justify … the simplex algorithm has exponential worse-case behavior, and the only people who have ever cared are the theorists. What you need to argue is (a) the average-case asymptotic behavior is important; (b) the average-case asymptotic behavior and worst-case asymptotic behavior are quite often similar; (c) the worst-case asymptotic behavior is often much easier to calculate than the average-case asymptotic behavior (especially since nobody knows what the relevant probability distribution is).  
> **username_0**: @PeterShor average-case becomes very weird for natural systems when we don't really give them inputs. For instance, if we are trying to argue that the [Arrow-Debrue model](http://en.wikipedia.org/wiki/Arrow%E2%80%93Debreu_model) is not the full story, we can say that using it (without further restrictions on the structure of markets considered) clashes with the popular assumption of "relatively quick" market equilibration. How can we possibly argue for a distribution over markets here? Aren't we just doing a philosophical analysis of if our assumptions fit? Or is such analysis of no interest?  
> **username_0**: @PeterShor any tips/advice on arguing part (b) in your recipe? Or is this completely problem/context specific?  
> **username_2**: As Peter says, it's very difficult to justify worst-case analysis. A much "easier" explanation is to demonstrate that an algorithm with good worst-case guarantees is in fact better in practice. A set of such cases is more compelling than any argument from principle.  
> **username_0**: @SureshVenkat but how do we do that when what we care about is lower bounds? In particular, my urge for using complexity arguments in fields like biology is specifically because we currently have no way to argue about certain microdynamics and thus no access to specific algorithms.  
> **username_1**: @Artem: I know a little bit about biology … it would really help me if you gave some specific examples of the kind of thing you are talking about.  
> **username_0**: @PeterShor To shamelessly push [my own preprint](http://arxiv.org/abs/1308.5094): there the goal is to use _very_ simple TCS to point out that "being at a (local) fitness peak" is an unreasonable assumption and should not be so freely made, contributing to a discussion in biology spurred by the [recent results from the Lenski's LTEE](http://telliamedrevisited.wordpress.com/2013/12/08/what-weve-learned-about-evolution-from-the-ltee-number-2/). To avoid being too chatty, I'd be happy to continue [on this blog post](http://egtheory.wordpress.com/2013/08/31/evolutionary-equilibria/) or by email.  
> **username_3**: Asymptotics is already a problematic aspect. We all know the story about matrix multiplication algorithms (asymptotic upper bounds are meaningless in practice), and perhaps also the story about choosing parameters in cryptography (asymptotic lower bounds are meaningless in practice; exponential algorithms are sometimes feasible [DES]). If your analysis has actual constants then it is more convincing.  
> **username_4**: I agree with everything that's been said so far, but want to add one point about [B]. In some sense, your response should be: actually, we don't care about the worst-case or the average-case, because (as you say) biology is typically not at equilibrium. The issue is that no one has a good model that produces something which "looks like" the real-world case. This is the source of a lot of work on generative models of networks that "look like" real-world networks. As to why worst-case, I'd stick with Peter Shor's argument, *especially* (c) - often worst-case analysis is the best we can do.  
> **username_5**: If you think about computation as a game (i.e., war) between the input provider and the algorithm, then the worst case analysis is a standard military approach - you want to know how bad can it be. Secondly, and more importantly, worst case analysis does not allow you to be intellectually lazy and accept solutions that might be good to what you believe the world is (and not what the world is really is). Finally, and maybe most importantly, it provide a uniform way to compare algorithms in a hopefully meaningful way. In short, it is the worst approach, except for all the others.  
> **username_6**: @PeterShor your comment makes a good answer.  
> **username_0**: @SarielHar-Peled I like the "does not allow you to be intellectually lazy" argument, but for lower bounds people can just argue "you are just picking this family of instances to prove your point, and is not a good description of how 'real' instances 'really' are", so it would have to be given more carefully to avoid this response.  
> **username_0**: @YuvalFilmus I agree that it is better to keep constants around, but sometimes (I would even say, oftentimes for lower-bounds) it is impossible. A classic example would be that additive constants are meaningless in Kolmogorov complexity. In my specific case, I am using TCS because it allow making minimal assumptions about underlying dynamics. i.e. I can't specify my model of computation (that would be assuming to much on the microdynamics) beyond saying it is 'reasonable' (for instance, doesn't grow resources super-polynomially) and that makes constants (and sometimes larger terms) meaningless  
> **username_0**: @JoshuaGrochow I agree very much. I actually use the unreasonableness of the worst-case results to argue that we need to think about a particular problem away from equilibrium. I also like (c) as a justification for worst-case analysis in TCS, but in biology I actually make a (c)-like argument against using the more common equilibrium analysis, and so my hands are a bit tied.  
> **username_4**: @SarielHar-Peled: +1 for "Worst-case analysis is the worst approach, except for all the others" :).  
> **username_7**: Worst case analysis is as useless as frequentist statistics. It answers a question no one has asked you (what is the worst possible scaling of your algorithm over all possible inputs and an unbounded input size) just as frequentist stats answers the question "What is the probability of the data given the model?" when you clearly want to know the probability of the model given the data (i.e. is he guilty?).  However both have turned out to be quite useful...  
> **username_8**: I think a worst-case lower bound should be seen as putting the ball back in their court. You have shown that there is no algorithm that can solve their problem on all instances in a reasonable time frame. They may reasonably believe that their instances are easy -- but you have just shown that if this is so, it is a non-trivial fact. Their model is therefore incomplete unless they come up with an explanation for why this is so.  
> **username_8**: (This is the approach that seems to work when talking to game theorists. It raises the question -- if markets truly equilibriate quickly -- what special property do real markets have that gets around worst case hardness? It is likely possible to define a plausible such property, and the lower bounds just suggest that doing so is an important research direction)  
> **username_0**: @AaronRoth this is my thinking as well. Do you know a source outside of econ (or comp sci, or math) which expands on these ideas?  
> **username_9**: Aaron makes a great point.  However, I'm not sure arguments that work in the presence of markets, where there are incentives to seek out the extreme behaviours that maximize gains, apply also to biology.  Are the dynamics really comparable?  
> **username_10**: Speed of light, $C$, is very important to them, see [Grace Hopper's lecture](http://www.youtube.com/watch?v=JEpsKnWZrJ8). If you give them a lower bound on a distributed algorithm every message passed is going to incur a lower bound of $C * distance$ no matter how big their research budget is.  
> **username_11**: @PeterShor, For simplex worse case I do not think that we can compare it with usual algorithms, simplex can solve some NP-Complete problems in its worst case scenario,so that worst case probably is not bad (it's meaningful), take a look at this paper: http://arxiv.org/abs/1311.5935.  
> **username_1**: @Saeed: For simplex simply viewed as an algorithm for solving linear programs, I think you can compare it with the usual algorithms; simplex doesn't solve NP-complete problems unless you pick a particular instantiation of the simplex algorithm and start worrying about its inner workings.  
> **username_12**: are you guys all overthinking this? worst case analysis is just a simple/basic _mathematical property_ of algorithms. it is a _fundamental conceptual starting/launching point_ for understanding more subtle nuances of performance such as how average case behaves (which is more based on _statistics_). worst case analysis focuses by nature on _extremes_. as for significance of average vs worst case how about the toy/universal model of [sorting algorithms](http://en.wikipedia.org/wiki/Best,_worst_and_average_case#Examples).... & comparing bubble sort vs quicksort etcetera....  
> **username_12**: another field where there are good examples/"justification" is ***cryptography*** where the security of the algorithm ***hinges*** on the distinction. a supposed trap door function which is hard in worst case but easy in average case is ***worthless/insecure*** etc....  
> **username_0**: @vzn thank you for the feedback, the interest is sciences that are not directly related to computing. Hence, cryptography is not relevant to the discussion.  
> **username_0**: @AndrásSalamon you make a great point about markets potentially 'seeking' worst case behaviour. However, it isn't obvious to me that this is irrelevant for biology. The key feature there is historicity, so even if we can't make an argument for seeking the worst-case, we also can't make an argument for average case.  
> **username_12**: the [A]/[B] objections given by biologists listed in the question are interesting but seem almost to be maybe pushing against too much TCS _abstraction_ introduced into a field of more physical/concrete analysis.. and too much abstraction standing in way of applicability is indeed a legitimate complaint of practitioners to much of TCS research! it would be helpful if you could quote more at length the "objections" & fill out more context....  
> **username_11**: @PeterShor, I think if you didn't look at my referenced paper, is not bad to look at it's introduction and some definitions and theorems without going in details. They prove that simplex implicitly solves np-complete problems, the definitions are somehow technical but in my humble opinion their argument is reasonable, that means we can classify algorithms in another point of view, in this classification simplex is an algorithm with some (magical) power (in its worst case scenario). What I want to say is that, it's not a good way to compare simplex with ordinary algorithms.  
> **username_12**: how about as a _"justification" (still on the highly questionable premise it_ needs _one), [goedel invented it in a letter to von neumann](http://rjlipton.wordpress.com/the-gdel-letter/) over ½-century ago?_  
> **username_12**: ran across this similar question on [cs.se]: [Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms](http://cs.stackexchange.com/questions/3523/8)  

---

## 3 answers

### Answer by username_9 on 2014-01-30. Score: 7

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.

> **Comments:**
> **username_13**: I don't share your enthusiasm for ditching asymptotics in favor of precise bounds with definite constants. Asymptotics may be imprecise -- but they're usefully imprecise. They abstract over implementation differences for the same machine model. E.g., a sorting algorithm that was quadratic on 1950s hardware will still be quadratic on today's hardware. Furthermore, asymptotic formulas compose nicely. Linears and polynomials are closed under composition, for instance. (Note that arguing for better bounds on the average case compared to worst case is orthogonal from arguing against asymptotics.)  
> **username_9**: You are right in general, but there is a big difference between a small constant and one that is a non-elementary function of a relevant parameter.  
> **username_0**: I like this answer overall, but I agree with @brandjon that hiding constants is crucial. For me, the reason TCS is useful in biology is because it needs to make much fewer assumptions about micro dynamics than physics. However, if you don't make assumptions about the micro dynamics (I.e. the exact specification of the model of computation) then you can't get the constant factors out. The other useful feature of TCS is rigorous qualitative dichotomies (something that is easier to compare to the more qualitative observations in bio), usually to get these you also have to ditch constants.  
> **username_0**: @Erhart it required a pretty strong assumption about the microdynamics: that only comparisons are allowed. In an evolutionary biology setting, an assumption of that strength would be saying that only adaptive walks on point-mutations in asexual organisms are allowed (in this case we can also prove lower bounds where we know the constants).  
> **username_14**: As a side note, there are examples where worst-case analysis makes sense. For example, when you develop a library of general-purpose subroutines and do not know in what application domains they will be useful: you cannot possibly anticipate all cases of when and why someone will want to compute a minimum cost bipartite matching, for example. Adversarial settings, such as cryptography, are even more clear cut (however, in crypto you'd really like to know the constants when it comes to security parameters).  

---

### Answer by username_13 on 2014-01-28. Score: 4

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 \* 109 base pairs, and tell them it's O(1) since the size of the DNA sequence is fixed. ;)

> **Comments:**
> **username_2**: I like the fibonacci example :)  
> **username_4**: Re: your first paragraph: actually, that's almost exactly what a lot of complexity theory does. If a problem is EXP-complete, that means it requires exponential time on worst-case inputs. This is generally taken as an indication of its overall difficulty (which, to be fair, in practice is often not so bad as a  general indicator). This is the de facto standard, called an "infinitely-often" or i.o. lower bound; getting average-case or almost-everywhere lower bounds (that is, for all but finitely many inputs) is a goal sometimes pursued, but often far out of reach compared to i.o. lower bounds.  
> **username_1**: Let me point out that not only can you give a laundry list of algorithms for which worst-case and average-case analysis are the same, but you can also give numerous examples where they are very different (the simplex algorithm just being the most famous of these). You really need to argue somehow that they are the same for your particular application; experimental testing is a good way to do this.  
> **username_13**: @JoshuaGrochow Fair enough. How about we revise the statement as follows: Lower bounds on worst-cases are important when you want to demonstrate the absence of a mathematical guarantee of non-horribleness. ;)  

---

### Answer by username_12 on 2014-01-29. Score: -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](http://www.cs.otago.ac.nz/staffpriv/mike/Papers/Wand/Wand.pdf) 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 scientiﬁc wing.
  > The engineering wing consists of well-understood design methodologies
  > while the scientiﬁc 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 oﬀered.
* [Complexity and Algorithms](http://www.cs.uu.nl/groups/AD/compl-diaz.pdf) J. Diaz. 100 slides. broad; one could excerpt relevant ones in particular.
* [A Gentle Introduction to Algorithm Complexity Analysis](http://discrete.gr/complexity/) 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](http://lazowska.cs.washington.edu/fcrc/Christos.FCRC.pdf) 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.

> **Comments:**
> **username_15**: I don't think this really answers the question.  
> **username_12**: uh huh, did you look at _any_ of the refs? part my answer is that there is not _(yet)_ any ideal/perfect answer :|  
> **username_15**: They seem to define asymptotic and worst case analysis rather than focusing on justifying it, but maybe I missed something?  
> **username_12**: seems to me all the refs have substantial-to-strong elements justifying the use of complexity theory (analysis) of algorithms in general outside TCS to scientists, engrs, researchers etc... wasnt that clear looking at them? (concede already it would indeed be better if something was written by a leader in the field...have not found that)... re asymptotic vs worst case, is the question really focused on that? _cant tell_ ... maybe researchers outside the field are unlikely to consider this distinction as crucial/pivotal as those inside of it ... & likely too specialized to find that ref ...  
> **username_4**: Actually, I think researchers outside TCS could easily dismiss worst-case as "artificially constructed examples that would never occur in practice" and would be (without strong convincing otherwise) much more interested in average-case (despite the fact that it's not clear that the average-case is that much closer to real-world instances).  
> **username_12**: seems to me for many algorithms & data that arise in practice (eg random instances of NP complete problems), average and worst case performance are related, so practitioners need to understand basic concepts of TCS (such as "easy" vs "hard" instances and "easy" vs "hard" problems and "inefficient" vs "efficient" algorithms & how these are scientifically quantified) but do not nec have to be so attentive to complexity-theoretic distinctions about performance that TCS researchers meticulously focus on. (and thought this pov is in line with the request in the original question, is it not?)  
> **username_12**: @joshua more thinking on this, dont understand why TCS theorists would find it nec to _"justify"_ worst case analysis. the origins of this theory in [Big-O notation (Laundau functions)](http://en.wikipedia.org/wiki/Big_O_notation) are from earlier _mathematics_ & even number theory. it is _intrinsic_ to complexity theory, virtually a _fundamental theorem_ that algorithms have complexity that can be measured. also that concept can be used for other than algorithm speed measurement, eg population growth etc.; outside of that there are subtleties/nuances that deserve further attn...  
> **username_12**: moreover if practitioners didnt care about _worst case_ they would be using _easier-implemented_ $O(n^2)$ _bubble sort_ instead of $O(n \log n)$ quicksort where the latter is harder to understand/implement.... are we sort of getting _wrapped around the axle here_ in this discussion....?  
> **username_4**: @vzn: Asymptotic (e.g. big-Oh) and worst-case are somewhat orthogonal. One can do asymptotic worst-case analysis, asymptotic average-case analysis, or even asymptotic *easiest*-case analysis (though I admit the latter seems somewhat perverse). One could instead do *exact* worst-case analysis, or *exact* average-case analysis, and so on, though these would be much more model-dependent and less robust. Justifying the use of asymptotics (and hiding things like constant factors) is entirely distinct from justifying worst-case vs average-case or "real-"case (whatever the latter might mean...).  

---

