[Question] What Are The Preconditions/​Prerequisites for Asymptotic Analysis?

[DragonGod]

Under what conditions is describing the behaviour of a (physical or abstract) process using asymptotic apparatus sensible/​productive/​reasonable?

Kinds of replies that I would find especially valuable:

• Formal properties that a function (or collection thereof) must satisfy for applying asymptotic analysis to be sensible

• Heuristics for when applying asymptotic analysis to real world processes is productive

• Examples of real world processes satisfying the above

• Examples of processes/​functions that might seem amenable to asymptotic analysis but which it would actually be a mistake to try and consider through an asymptotic lens

[tailcalled]

Asymptotic analysis tends to be useful when you expect the function to take large values as input, but don’t necessarily know how large they will be. For instance, knowing that the asymptotic complexity of sorting is $O\left(n\log n\right)$ isn’t all that useful when you are solving a list of 7 elements; it’s mainly useful when considering sorting lists of 1000000000 elements (where you can infer that e.g.$O\left(n^2\right)$ would be too expensive but $O\left(n\log n\right)$ is not).

I guess it is also sometimes useful as a sort of “interpolation strategy”. Like if you want to know the properties of a function, you can first asymptotically characterize its limiting properties, and that covers a good chunk of the information about the function, leaving you only with a bounded area of uncertainty. Then you can analyze how it shifts between its asymptotes in the middle.