by Rishidev Chaudhuri
Asymptotic reasoning is ubiquitous in mathematics and the natural sciences, representing both a general approach to problems as well as a collection of techniques. It is one way of answering the question, “Which features of the world are relevant for our understanding?” Often, the behavior of a system gets simpler as it gets larger: only some of the features that are relevant for understanding a small system are necessary for understanding a very large one. The averaging out of fluctuations in the long-term is perhaps the most obvious example of this. Asymptotic analysis attempts to describe the behavior of an object (function, physical system, algorithm) as some quantity gets very large or very small. It is thus fundamentally the study of particular sorts of approximations, albeit approximations that can be made as precise as one wants, and a guide to which features of an object can safely be ignored.
To start with a simple example, look at what happens to the square of a number and to its cube as the number gets bigger and bigger. Both the square and the cube race off to infinity, but one does so faster than the other. 13 and 12 are the same; 23 is twice as big as 22; 33 is thrice as big as 32 and so on. For any number N, N3 is N times as big as N2, and as N gets really big the function N2 is dwarfed by N3. So to see how the behavior of a function could become simpler as it approaches infinity, look at the behavior of
N3+N2
If we are thinking asymptotically, we would say that this function behaves like N3: for any degree of approximation we choose the contribution of N2 will be irrelevant for large enough N. Here “large enough” depends on the degree of approximation we want. If we decide that irrelevant means “contributes less than 1% to the value of the function”, then N2 is irrelevant once we reach N=100; if instead we decide that it means less than 0.01%, then we must wait till N=10,000, and so on. The crucial point here is that we can satisfy any desired degree of approximation, no matter how stringent.
