2

An asymptote in mathematics represents a value (line) to which the observed function constantly approaches. In other words, as the value of X increases towards infinity, i.e. decreases towards minus infinity, the value of the function approaches that value/line (asymptote).

When we talk about the big O notation, such a value/line (asymptote) that the function (description of the algorithm) approaches does not exist, so I wonder why the big O notation is defined as the asymptotic analysis of the algorithm? What does asymptotic mean in the context of algorithmic analysis? I know that the big O notation represent upper bound of the function that represents algorithm, so does that upper bound has something with the asymptote?

9
  • Why do you say that such asymptote does not exist for the analysed function?
    – Bergi
    Oct 16, 2023 at 12:43
  • @Bergi For example, if we have functions f(x)=2x^2+20x and g(x)=4x^3. g(x) is not an asymptote to the function f(x), but it is an upper bound.
    – dassd
    Oct 16, 2023 at 13:07
  • Ah well to find the asymptote itself, try Θ (big Theta) notation instead… But even if 4x^3 is not the asymptote in your example, that's not the same as saying no asymptote exists.
    – Bergi
    Oct 16, 2023 at 13:21
  • @Bergi It seems that indeed g(x) is not an asymptote for f(x). See Doc Brown's answer below. He explained it very well.
    – dassd
    Oct 16, 2023 at 13:25
  • @Bergi: any suggestion of what the asymptote of ` f(x)=2x^2+20x` might be? Hint: g(x)=2x^2 would be wrong, since |f(x)-g(x)| is not converging to zero.
    – Doc Brown
    Oct 16, 2023 at 13:45

7 Answers 7

19

An asymptote in mathematics represents a value (line) to which the observed function constantly approaches.

Well, that is a narrow definition of the term asymptote. A more general definition allows also non-linear curves as asymptotes. The english Wikipedia currently leaves this point-of-view out, but other sources like the german Wikipedia mention them.

This is, however, not the full story, since in context of big-O, f(x) = O(g(x)) does not mean g(x) being asymptote an for f(x). To express the difference, in computer science, we usually say that g(x) is an "asymptotic upper bound" for f(x). Formally, this means

lim sup  |(f(x)/g(x))|  = c    for some non-negative real value c < ∞
  x->∞

Hence, the value c ( or line "y=c") is indeed an asymptote for |(f(x)/g(x))| ( to be precise: for h(x)= sup{|(f(t)/g(t))| : t > x}. This is sometimes confused with g(x) ( or c * g(x)) being an asymptote for f(x), which is mathematically not correct.

So yes, the usage of the term "asymptotic" in computational complexity may not be exactly the same as in other mathematical fields, but it is clearly related and can be interpreted in a way it points back to it's origin, using strict mathematical definitions.

31
  • 1
    @joke: c is an asymptote for |f(x)/g(x)| (absolute value!). And you are right, c can be zero, for "big-O", see my edit. The term "asymptotic upper bound" is just the term CS people use for this, see my other edit.
    – Doc Brown
    Oct 16, 2023 at 12:48
  • 2
    @joke: when using the |f(x)| < c|g(x)| ... definition (instead of the lim sup definition) for big-O, choosing c=2 would be wrong, since 2x^2+10x is never smaller than 2x^2 for all x >0. But when you pick c = 2.001, or c=2 + ε, where ε is some value >0, then the condition will hold for all x beyond som x0.
    – Doc Brown
    Oct 16, 2023 at 13:30
  • 1
    @joke All correct, except this: "That is why we calculate |f(x)/g(x)|. If this is < 1 for all values as x goes to +inf, we would have an upper bound. However, in the context of Big O notation, bound has different meaning and it is only important that it goes towards some non-zero value as x goes to infinity." The quotient |f/g| doesn't have to "go towards some non-zero value", it only has to "become bounded" ie at some point it stays below some constant value. (And if f is a function of integers only, then "become bounded" and "is bounded" are equivalent)
    – Stef
    Oct 19, 2023 at 8:14
  • 1
    @joke: Stef is right. For example, think of a function like this: f(x)=2*x^2-20x+4 when x is an even integer, f(x)=0 for each odd integer. Still f would be O(x^2). I added a small clarification to my answer.
    – Doc Brown
    Oct 19, 2023 at 9:36
  • 2
    @joke: lim sup |f(x)/g(x)| (with x->inf) exists - it is 11. See en.wikipedia.org/wiki/Limit_inferior_and_limit_superior
    – Doc Brown
    Oct 19, 2023 at 13:22
20

What does asymptotic mean in the context of algorithmic analysis?

It means that someone, at some point during the last 130 years, looked at Bachmann-Landau notation and thought "Hey, this looks kinda-sorta like what we use asymptotes in analytic geometry for, so let's call it asymptotic analysis.

No more. No less.

In particular, since asymptotes are a concept from analytic geometry, and this is not analytic geometry, there can be no expectation that the term means the same thing.

In analytic geometry, an asymptote can be used as a rough idea of how the graph of a function f(n) behaves as n grows large. Bachmann-Landau notation can be used as a rough idea of how fast a function f(n) grows compared to another functions g(n) as n grows large.

That's all there is to it.

3
  • Hey Jörg, It seems that you are the only one who really understood my question and what is the source of my misunderstanding. Thanks for that. So, while in mathematics we could represent asymptotes through two things: 1) X grows towards +/- inf 2) based on (1) the function f(x) goes towards some value/line (asymptote). In the analysis of algorithms, there is only (1) from mathematics, while (2) is defined differently. That (2) in this case would represent the way in which the function grows as X increases (nature of growth) in comparison with some standard classes defined through g(x).
    – dassd
    Oct 16, 2023 at 10:55
  • Therefore, there are no real asymptotes as in mathematics, i.e. there is nothing to which the function f(x) (the one we observe) goes. Here, the term "asymptotic" is taken on the basis of point (1), i.e. on the basis that we observe the behavior of the algorithm as X grows towards infinity, but not in the context of approaching some value/line (asymptote in mathematics) but in the context of the nature of growth in comparison with some standard classes defined through g(x) such as n, n^2, logn. Therefore, the upper bound O(n) is not an asymptote. Did I understand correctly?
    – dassd
    Oct 16, 2023 at 10:55
  • 12
    This is not bad answer, however, I think the term "asymptotic upper bound" in computer science is stronger connected to asymptotes from analytical geometry than just "it looks somewhat similar".
    – Doc Brown
    Oct 16, 2023 at 18:41
10

I think you're overthinking the whole asymptotic "but never reaches" aspect, that's not terribly important. Also, forget about trying to incorporate a bunch of grad-school level math, that just really isn't important here either.

Big O is just to describe how the runtime of a function grows as its input grows to be Huge™ in size. Huge™ is a sufficiently technical quantity. We programmers are regularly using the same 'tool' to work with data sets that span several orders of magnitude in size, this is something that is basically unique to this field. The same code might be use to select which choice from a vending machine, as to select one of trillions of records, (aka Huge™). In no other field does that sort of thing take place.

So, when are running our algorithm on those datasets several trillions of records in size, all the hardware quirks, constant factors, and other trivia is shaken out and becomes a rounding error compared to those resulting Big O factors. We're never going to approach infinity because we're probably never going to have harddrives the size of the solar system, so we just kinda play fast and loose and deciding when we're big enough.

When we're doing the math to actually compute the complexity of an algorithm, we can compare asymptotic aspects of each contributor to the growth to decide which are important and which are not, which can be some tricky grad-school math. But you may have intuitively realized some of it, in your comment f(x) = 2x^2 + 4x + 30 it should be plain to recognize that as x gets Huge™ only x^2 is going to matter, and the others are rounding noise. For a simple example we can intuit that plainly, but to formally prove it in a grad-school level class we need to use limits and all the asymptotic math you're fretting about.

But to compare algorithms that have been analyzed, we don't have to think nearly as hard.

1

Some vocabulary and theorems and notations to reconcile the geometry of asymptotes and asymptotical analysis.

A bit of vocabulary:

  • A function g is an asymptote of function f at +oo if the absolute difference |f-g| tends towards 0 at +oo.
  • A function g is a linear asymptote of function f at +oo if g is an asymptote of f and g is a linear function.
  • A function g is an asymptotical upper bound of function f at +oo if f ≤ g in the neighbourhood of +oo.

A theorem:

  • A function f always has at most one linear asymptote at +oo.

A bit more vocabulary:

  • If f has a linear asymptote g at +oo, then g is sometimes called the asymptote of f at +oo.

And finally a bit of notation:

  • f ∈ O(g) means that there exists a constant K > 0 such that K g is an asymptotical upperbound of f.
14
  • Hey Stef, what do you think about Doc Browns answer and the way he explained it?
    – dassd
    Oct 16, 2023 at 14:16
  • 1
    The way he explained it was phenomenal. You have provided additional information and definitions, thanks for that. As far as I understand, g(x) represents the asymptotic upper bound of the function f(x), because when we put those two functions in the relation (f(x)/g(x)), g(x) limits the function f(x) in its growth . And in that way, with the growth of x towards inf in the ratio f(x)/g(x), g(x) prevents f(x) from growing but only goes towards some value (for example 2).
    – dassd
    Oct 16, 2023 at 14:55
  • 1
    Therefore, g(x) is not an upper bound for f(x) because there are no values of g(x) greater than f(x), for example f(x)=2x^2+10x and g(x) = x^2, for every x, f(x) is greater. Also g(x) is not an asymptote of f(x) because f(x) does not approach g(x). It is something between, an asymptotic upper bound. Am I right?
    – dassd
    Oct 16, 2023 at 14:56
  • 1
    @joke Yes, everything you said sounds right. I'd be careful though; the term "asymptotic upper bound" is often used somewhat informally without an explicit definition, and depending on context, "g is an asymptotic upperbound of f" might mean either "in the neighbourhood of +oo, g is an upperbound of f" or "there exists a constant K > 0 such that in the neighbourhood of +oo, Kg is an upperbound of f".
    – Stef
    Oct 16, 2023 at 14:58
  • 1
    @joke That depends on who is saying it. For some people the "asymptotic' in "asymptotic upperbound" just means "in the neighbourhood of +oo", while for other people the "asymptotic" in "asymptotic upperbound" means both "in the neighbourhood of +oo" and "up to a multiplicative constant". In general, authors tend to not write down their preferred formal definition of "asymptotic upperbound" and you have to guess on context, but it's not too important because they will also use precise formal notation in addition to those not-explicitly-precisely-defined words.
    – Stef
    Oct 16, 2023 at 16:07
0

For Big O, the upper bound is the asymptote.

Big O notation doesn't tell you how long a method will take. It tells you how the shape of the worst case scenario grows as n grows. We expect how long the method typically takes to remain under this limit.

When we first learn about asymptotes in school they are simply straight lines with no curves. That isn't always the case here. These asymptotes can curve.

Big O is only one of the asymptotic notations.

4
  • The point of the asymptote in mathematics, as far as I know mathematics (and I don't know much of it) is that as X increases (decreases), our function approaches the asymptote, but never reaches it. With big O notation, this is not the case. If we have the function f(x) = 2x^2 + 4x + 30, the big O complexity, that is, the upper bound is g(x) = x^2. In what way does f(x) approach g(x) as x increases? I would say that is not the case here.
    – dassd
    Oct 16, 2023 at 4:03
  • Also, here they say that the big O notation is not properly definable in terms of limits (lim). And the answer below said in additional that the limits are wrong way of thinking about asymptotic notation and expansions.
    – dassd
    Oct 16, 2023 at 4:13
  • 2
    "For Big O, the upper bound is the asymptote." - not really. See my answer.
    – Doc Brown
    Oct 16, 2023 at 11:47
  • "It tells you how the shape of the worst case scenario grows as n grows." << Well, only if you're talking about the worst case scenario. You can also use big O to discuss the average time of execution, or the time of execution under a particular assumption, or anything else. Also, big O only expresses upper bounds, so the sentence "the time complexity is O(n^3)" would be correct even if the worst-case scenario actually was 10 n^2 log(n) and not n^3. (And this happens often in practice, because identifying and proving a tight upper bound could be much more complicated)
    – Stef
    Oct 16, 2023 at 14:02
0

There are many good answers already, but if you look at the Wikipedia entry for the word "asymptote", you find, amongst the modern mathematical definition, this nugget:

The word asymptote is derived from the Greek [...] which means "not falling together" [...]. The term was introduced by Apollonius of Perga [...] to mean any line that does not intersect the given curve.

The term O(n) means, according to Wikipedia's page on the O-notation:

f(x) is big O of g(x) if the absolute value of f(x) is at most a positive constant multiple of g(x) for all sufficiently large values of x

Visually, you can think of two curves going to infinity, with the curve y=f(x) not intersecting the curve y=c*g(x) for x greater than some value x0, and c positive. (If you are nitpicking, the definition of O allows for the two curves "joining", i.e. f(x) = c*g(x). But for some interpretation of "intersect" which allows the curves "bumping together" like that (just not passing beyond each other), this would be just fine. If it really bothers you, then define g'(x) = g(x)+1 to "unbump" the curves).

So while I have no idea why the first person using the word "asymptote" in this context actually did so, this seems like a very plausible explanation to me.

-1

It's just a name. Asymptotes in geometry do not have much in common with asymptotic analysis and you will get no insights in trying to find a logical connection between them.

There may be some historical / etymological reason why asymptotes and asymptotic analysis have a partially common name, but afaik those are almost unrelated in modern math. (The only similarity is that both deal with what happens "at infinity".)

To give another example which i find similar: The words "butter" and "butterfly" have very similar names, because people once thought these insects steal butter. But you can gain no insight regarding butter or butterflies when looking for a connection.

6
  • 1
    I completely disagree with your first paragraph.
    – Stef
    Oct 16, 2023 at 14:00
  • @Stef why? The only common thing is that both describe behavior at infinity. f(x) = x \in O(e^x) is a true statement, how would you relate that to any geometric asymptote?
    – AEF
    Oct 16, 2023 at 14:39
  • Because it's defeatist. There is definitively a connection, and there is definitively insight to be gained. In fact, if you look at the OP's comments on this page, it looks like the OP did gain a lot of insight by asking this question here.
    – Stef
    Oct 16, 2023 at 14:41
  • Yes, of course you can learn something from every question, so maybe my statement was too absolute. Still, I don't think that investigating this "connection" is very fruitful and I certainly don't think that advising a learner which questions lead to interesting answers and which don't, is defeatist. And it seems to me, that every insight OP gained by asking this question here could also have been gained by asking questions about asymptotic analysis alone.
    – AEF
    Oct 16, 2023 at 15:12
  • 1
    See DocBrown's answer for what they have to do with each other. In asymptotic analysis, we try to find a g(x) so that |f(x)/g(x)| has a horizontal (geometrical) asymptote.
    – Bergi
    Oct 16, 2023 at 21:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.