0
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ "we regard $n^2$ and $2n^2$ as asymptotically equivalent": where do you draw this from ? What is your definition of asymptotic equivalence ? $\endgroup$
    – user16034
    Commented Aug 30, 2023 at 7:09
  • $\begingroup$ @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? $\endgroup$
    – Kardashev Type V
    Commented Aug 30, 2023 at 8:45
  • $\begingroup$ @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. $\endgroup$
    – Kardashev Type V
    Commented Aug 30, 2023 at 10:08
  • $\begingroup$ First give us a reference of the definition of asymptotically equivalent that you found and made you ask this question. $\endgroup$
    – user16034
    Commented Aug 30, 2023 at 12:18
  • $\begingroup$ @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. $\endgroup$
    – Kardashev Type V
    Commented Aug 31, 2023 at 11:20

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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/…. $\endgroup$
    – user16034
    Commented Aug 30, 2023 at 7:15
  • $\begingroup$ @YvesDaoust, good point. I've edited my answer. Thank you for the feedback. $\endgroup$
    – D.W. ♦
    Commented Aug 30, 2023 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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