What is an asymptote?

Question

In a reply came the term asymptotic. In comment came a definition.

I think it would be to have a more complete definition here. But the focus of the question is even simpler:

In Portuguese clear, even if inaccurate, what does this mean for the programmer who does not have a good mathematical basis? Why does it matter to him?

For the average programmer this is not clear and what this matters:

In mathematics, an asymptote/asymptote of a curve C is a point or curve from which the points of C approach as one traverses C When C is the graph of a function, in general the term asymptote refers to a line.

Answer 1

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):

• How to prove the asymptotic order of an algorithm?
• Is there any sort algorithm that actually runs on O(n)?
• Time consumption in cubic code
• How to improve my code performance with "for"?
  Special note: in this question, the author believed to have 3 for nested within each other was a sign of inefficiency, but he had not realized that he was at the best mathematically possible to iterate in a "cubic" collection of data
• Time complexity of recursive palindromic algorithm
• What is the best implementation of 'Mergesort Algorithm'?

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:

1. conjecture OA
2. debt^* F/OA or OA/F
3. 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:

• Testudo marginata (GPL): https://en.wikipedia.org/wiki/File:Nacht_006.jpg
  The gif deal with it, Achilles therefore should also be used under the GPL
• 1 on x: https://en.wikipedia.org/wiki/File:Hyperbola_one_over_x.svg
• Achilles and the turtle: https://en.wikipedia.org/wiki/File:Zeno_achilles_paradox.png
• Plotting functions obtained from Wolframalph queries:
  • f(t) = e^(-0.1 t)
  • f(x) = sin(10*x)/x + x vs g(x) = x
  • f(x) = |1/x| + x**2 vs g(x) = x**2

Answer 2

I will be as brief and simple as possible and concentrate on responding:

1. What this means for the programmer who does not have a good mathematical basis?

   This is my case, I do not consider to have a good mathematical basis. But for me, the concept: asymptote leads me to think about Asymptotic Notation relates to the algorithm analysis and is used as a analysis tool for the purpose of: Análise Assintótica. In this way, we can assume that:

   In general, each step in a pseudo-code description or implementation in high-level language corresponds to a small number of primitive actions (except for method calls, of course). Thus, we can perform a simplified analysis of an algorithm written in pseudocode that estimates the number of primitive operations executed, except by a constant factor, counting the steps of pseudocode (but one should be careful since a line of pseudocode may denote several steps in some cases).[Goodrich, Michael; Tamassia, Roberto - 2007, 159 p.]

   For that we use the Asymptotic Notation, a good example: Big-O (see definition here: [Luiz Vieira - 56868], very well answered by the way), omega: Ω and theta: θ are very convenient because they allow concentration on the general aspects instead of the details.

2. Why it matters to him?

   When we assume the role, that is, we use the "cap" of programmer is very important, in the algorithm analysis focus on the growth rate of the running time.

   And it is important to know how to differentiate efficient and inefficient algorithms, it is natural to make this distinction between the algorithms that run in polynomial time and those that require exponential time respectively.

   That is, the distinction is made between algorithms that run in time O(n^c) for any count c > 1 and one whose execution time is O(bⁿ) for any account b > 1. ([Goodrich, Michael; Tamassia, Roberto - 2007]).

   Based on this we can use the complexity graph below to make the distinction visually.

   _{Figure: Graph showing the relation of Big-O notation and its complexities
   SOURCE: [Maniero - 268308]}

   And of course it’s important for the programmer to know that:

   One can use the Asymptotic Notation The (Big-O) to sort function classes by their asymptotic growth.

   That is, if a function f(n) precedes a function g(n) in the sequence according to the table below:

   f(n) is O(g(n))

   _{Table: ordered sequence of function classes by their asymptotic growth
   SOURCE: Prepared by the author of the answer.}

---

_{Note¹: as to the mathematical basis, we will say that we must maintain the practice habit, making lists of exercises, of the functions (mathematical facts) applicable in the algorithm analysis.}

_{Note²: In the table above, I assumed the criterion of efficient and inefficient only because it is very convenient because it is to concentrate on the general aspects, instead of the details.}

---

Reference:
_{[Goodrich, Michael; Tamassia, Roberto - 2007], 4 ed. - Porto Alegre: Bookman 2007, Java data structure and algorithms: 4 Edition.
[Maniero - 268308], Stack Overflow , Answer: How can I improve my code performance with "for"?. Accessed: 14 Jan. 2018
[Luiz Vieira - 56868], Stack Overflow , Answer: Definition of the notation "Big O". Accessed: 14 Jan. 2018}