A Greek tale
The asymptote of Achilles is the tortoise
Corollary of Paradox of Zeno
One day, Achilles the Hero and a turtle fought. The turtle stated to Achilles that if she started ahead, she would win a race of any distance against Hero. Curious, Achilles asked
-Why is that? If I’m faster than you, I’ll win.
Then the turtle will answer:
-If I start at the front, you must first reach the position I was in. But by the time you get there, I will have walked, I will be further along. Then you will have to reach my new position, and I will be in front of you. Then you will need endless steps of these until arrive in me, because then to overcome me will need more than infinite steps.
Informal notion of asymptote
In Zeno’s paradox, no matter how many times Achilles tries to overtake the turtle, he never will. For, at every step, Achilles is approaching the turtle. Achilles becomes asymptotically close to the turtle.
See the following infographic, evolution of Achilles and turtle positions:
You can see that Achilles gets closer and closer to the turtle every time. This type of behavior we call asymptote. Hence, the asymptote of Achilles is the turtle.
When you want to know the general behavior of a function, you want to know what the asymptote function. For example:
To infinity, this function tends to have the same behavior as x^2
. So we can say that the behavior of f(x) = (x^2 - x)/2
is asymptotically x^2
.
This has practical application?
Well, that means that the Bubble Sort it gets worse so fast when the Insertion Sort, and also that the merge Sort will be better in larger cases. Later, ne section Why it matters to the programmer?, I will carve more.
How to identify asymptotes?
In general, you need an "Achilles" and a "turtle". The turtle will be the asymptote of Achilles.
The function given as an example it approaches x^2
, but never comes to it.
Another case too, I could take over the function 1/x
. In the positive infinity, it tends to be zero, but never is:
Note that when x=10
, the function is worth 0.1
. When x=80
, the function in turn would now be worth 0.0125
. Getting closer and closer to 0, but never actually getting there.
Why it matters to the programmer?
In a normal world of enterprise applications that do not care about calculating what discount (in percentage) I should apply in the selling price so that the value with the ICMS-ST reaches the total of R$10.00 in the final price (tip: has a formula that condenses the infinite sum), asymptotes serve basically to describe algorithmic behaviors.
So for the average programmer, what matters is asymptotic behavior, normally associated with the time/spatial complexity of an algorithm.
The following is a list of questions that flirt with this concept (author knowing this or not):
In all cases, one asks for something in relation to asymptotic behavior (or as part of the answer, or as part of the question).
It also goes for the programmer to know that asymptotic behavior is not always everything. Sometimes we have hidden constants that when we are not "chasing turtles into infinity" become much more important. For example, the Quick Sort has the running time normally faster than the merge Sort.
How to prove the asymptotic order of an algorithm?
This question already has an answer here:
How to prove the asymptotic order of an algorithm? 3 responses
Formally, what is an asymptote?
An asymptote is a point or curve to which a function tends. For example, the center is the asymptote for the following exponential polar function:
It is plotted like this:
The higher the θ, the closer the function is to (0,0)
. So (0,0)
is the asymptote of f(t) = e^(-0.1 t)
.
A curve can intercept your asymptote. For example, f(x) = sen(10*x)/x + x
has as though g(x) = x
:
Not every asymptote needs to be a straight, but it can be a curve. As the case of f(x) = |1/x| + x**2
, whose asymptote in infinity is g(x) = x**2
:
So, the asymptote A
of a function F
is a value (example of spiral) or function (other two examples) which, given the evolution of F
in terms of some variable, F
approaches arbitrarily close to A
.
How to discover an asymptote of a function?
I usually use the following steps (for functions that use Cartesian coordinates, not polar) to find out the order of the asymptote:
- conjecture
OA
- debt*
F/OA
or OA/F
- made a mistake, repeat
The division, however, cannot be done in any way. Normally, if you want to know what the extreme behavior of the function is, then the division is with the limit of the variable going to infinity. In this case of infinite behavior, OA
is of the same order as the F
if they are co-dominant as defined in this response:
Also condensed in that @Isac response for the same question (Obs: with c != 0
):
Once the order is discovered, the value obtained by the division is the coefficient of the highest term. This means that the most significant term of asymptote has known coefficient, c
. Now, remove the most significant term and calculate again. How?
Well, we found OA
the co-dominant function of F
. We know that F = OA * c + G
, for c = lim OA/F
. So now is to find the value of G
and add to c*OA
, doing this recursively until at some point, lim G = 0
. This will be the asymptote curve of F
.
Example
To f(x) = x + sen(10*x)/x
. Let’s first assume that the order of the asymptotic function OA
is x**2
:
That split gives 0, so OA
domina f(x)
. Therefore, the first conjecture of the asymptotic function order went wrong. In this case, let us repeat.
Let us now assume that the order of the asymptotic function OA
is x
:
They’re co-dominant, so the asymptotic order is really, OA
. For the next step, we need to remove c*OA
of f(x)
and check g(x)
:
We have come to the conclusion that g(x) = sen(10 x)/x
. Now, we need another term to define the asymptote of g(x)
?
No, we don’t. So, A(x) = x
is the asymptote for f(x) = x + sen(10*x)/x
.
There are other asymptotes than infinity?
Yes, there are. Usually, they find themselves in points of discontinuity.
Take the hyperbole f(x) = 1/x
:
It presents discontinuity in x = 0
. So the point x = 0
is a candidate to be a upright asymptote of the function. To find a vertical asymptote in the point x = a
, one of these four criteria must be met:
The function must tend to infinity (positive or negative) when x
tend to value a
, either the limit on the left or the limit on the right.
In the case of hyperbole, when x -> 0
on the right, f(x) -> +infinito
. That’s enough to consider x = 0
vertical hyperbola of 1/x
.
Image sources:
lim x-> N F(x)/G(x) = k
forN pertencente R + { -infinito , +infinito }
andk pertencente a R*
implies thatG
is asymptote of functionF
at the pointN
(or in the infinite). It is not quite right but it is very close– Jefferson Quesado
And nothing clear :D
– Maniero
The asymptote of Achilles is the tortoise
– Jefferson Quesado
Less and less clear :D :D :D
– Maniero
There’s an example to add to that definition ? @Maniero
– Fernando Souza
@Fernando this question provides examples of asymptotes for the time complexity of an algorithm, and the answers deal with other algorithms as well: https://answall.com/q/236960/64969
– Jefferson Quesado
@Fernando I don’t know if it’s the focus, but it’s a suggestion for those who answer.
– Maniero
This term was used in this note: Note here another mathematical property that moves the real possibilities away from the theory, forcing the subject who uses Gaussian statistics to platonify. CONTINUES...
– user60252
In the real world, by time limit, resources or data availability, we are almost always required to work with small sample sizes, far from being considered reasonable for good approximations, in the sense of the "Law of Large Numbers" and the "Central Limit Theorem". CONTINUES ...
– user60252
I mean, we don’t live in the;
assíntota
. Often, in statistical courses, teachers stipulate a magic number, such as n=30, as being large enough to allow good approximations. Of course, this only makes sense if some strong hypotheses about the nature of the variables are made a priori, such as believing that they have Mediochristian behavior (often a strong Platonification): a "banana peel" to fall into the playful fallacy. http://www.econ.puc-rio.br/uploads/adm/trabalhos/files/Bruno_B_de_Oliveira.pdf– user60252