# Asymptotic equivalence allows difference by a constant factor?

Wikipedia and other sources define "asymptotically equivalent" as: two functions $$f$$ and $$g$$ are asymptotically equivalent if:

$$\lim\limits_{x \to\infty}\frac{f(x)}{g(x)}=1$$

But we regard $$n^2$$ and $$2n^2$$ as asymptotically equivalent, and these always have a ratio of 2 between them. Is there a different definition of "asymptotically equivalent" that I should be using?

This MIT Problem Session from 2020 illustrates calling $$n^3$$ and $$\binom{n}{3}=\frac{n(n-1)(n-2)}{6}$$ asymptotically equivalent. If you back up a bit from the time where the link starts, you'll see (actually, hear) the algebra spelled out.

• "we regard $n^2$ and $2n^2$ as asymptotically equivalent": where do you draw this from ? What is your definition of asymptotic equivalence ?
– user16034
Aug 30, 2023 at 7:09
• @YvesDaoust Well, I suppose I'm still looking for definitions, but I thought asymptotic behavior was commonly considered equivalent if both functions differ by no more than a constant factor. No? Aug 30, 2023 at 8:45
• @YvesDaoust Now I think I'm more confused. You said in this comment that "to a constant factor" is never regarded as equivalent to "asymptotically equivalent". Could you post an answer that spells this out clearly? If it's just a matter of competing terminologies, it would be nice to see them spelled out; or if there is something more to it, like reasons or contexts where one is preferred, it would be nice to see that spelled out, too. Aug 30, 2023 at 10:08
• First give us a reference of the definition of asymptotically equivalent that you found and made you ask this question.
– user16034
Aug 30, 2023 at 12:18
• @YvesDaoust Are you asking for a reference because that will help you write an answer, or as a pedagogical move to teach me to look up references? I am worried that this is a distraction from my question. I am asking on SE to get the benefit of other people's greater experience with the literature, the informal customs, and the subject matter itself. Aug 31, 2023 at 11:20

There are multiple notions/definitions of asymptotic. You need to pick one that is appropriate for your goals.

One approach to asymptotics is exactly as you have stated (see, e.g., https://en.wikipedia.org/wiki/Asymptotic_analysis). This notion cares about constant factors. It is commonly used in mathematics. Standard notation is $$f(x) \sim g(x)$$.

Another approach to asymptotics ignores constant factors. This is standard in computer science. In particular, we write $$f(x) = \Theta(g(x))$$ for two functions that behave the same asymptotically, in this sense. See https://en.wikipedia.org/wiki/Big_O_notation.

Which one to use depends on what you care about. In computer science, we often care about analyzing the running time of algorithms, in a theoretical model where we ignore constant factors... hence we typically use the second notion.

I have only ever heard the phrase "asymptotically equivalent" used for the first kind of use of asymptotics, but I don't know whether that is an accepted terminology or just my personal experience.

• I don't think that $f(x) = \Theta(g(x))$ are ever read as "$f$ and $g$ are asymptotically equivalent". They only are "to a constant factor". Also check en.wikipedia.org/wiki/….
– user16034
Aug 30, 2023 at 7:15
• @YvesDaoust, good point. I've edited my answer. Thank you for the feedback.
– D.W.
Aug 30, 2023 at 16:47