2
$\begingroup$

Let $f(x)= 5x^3+x.$

A) I'm just learning the Big O notation, and my study materials indicate that since $f(x)$ is $O(x^3),$ $f(x)$ is asymptotically dominated by $x^3.$

B) On the other hand, I know that $f(x)$ is asymptotically equivalent to $5x^3.$

C) Hence, as $x$ approaches infinity, $5x^3$ is dominated by $x^3,$ which is clearly a contradiction.

What gives?

  • 1
    It would probably be best to refer to the technical definition of big-O. What does it mean to say that $5x^3+x = O(x^3)$? Is $5x^3 = O(x^3)$?2012-03-24
  • 0
    The big O notation allows for a constant factor. That is, $f = O(g)$ means that there is a constant $C$ such that $f(x) \le C g(x)$ when the argument $x$ tends to the value of interest (e.g. $\infty$ as in your example). In your example any $ C > 5 , g(x) = x^3 $ will do :-). ($C=5$ won't, because of the $x$ term).2012-03-24
  • 0
    Thanks. So am I correct to surmise that f(x) is in fact *not* asymptotically dominated by $x^3$? I know the technical definition of Big-O, and am questioning why the author of my notes defines O(g) as "the set of all functions which are asymptotically dominated by g." There is another set of notes online from the Uni of Nebraska-Lincoln that states that big-Theta implies asymptotic equivalence. Are both authors wrong?2012-03-24

1 Answers 1

3

I have changed my answer significantly from its original form to reflect the discussion in the comments below and to directly answer the OP's revised question.

The problem seems to lie in the ambiguity of the terms "asymptotically equivalent" and "asymptotically dominated". It seems to me that they could each mean different things, and I discuss the possibilities below. I am not experienced enough to say which meanings are more common (though I will list the sources I know which use one or the other).

Asymptotically equivalent

In N. G. de Bruijn's book Asymptotic Methods in Analysis and on AOPS the convention is that
"$f(x)$ is asymptotically equivalent to $g(x)$" when $f(x) \sim g(x)$. That is, when $$\lim\,\, \frac{f(x)}{g(x)} = 1.$$

In Graham, Knuth, and Patashnik's Concrete Mathematics, this behavior is phrased as "$f(x)$ is asymptotic to $g(x)$".

Being more familiar with Concrete Mathematics, I originally assumed that when the OP spoke of
"$f(x)$ is asymptotically equivalent to $g(x)$" he was referring to the expression $f(x) = \Theta(g(x))$. That is, $$f(x) = O(g(x)) \hspace{1cm} \text{and} \hspace{1cm} g(x) = O(f(x)).$$ If $f(x) = \Theta(g(x))$ then the two can be said to share the same order of growth.

Asymptotically dominated

I'm not familiar with the phrase "asymptotically dominated", so I assumed "$f(x)$ is asymptotically dominated by $g(x)$" meant $f(x) = O(g(x))$. This relationship can be interpreted as $g(x)$ growing (respectively, shrinking) at least as fast (respectively, at most as fast) as the 'largest part' of $f(x)$, so that $g(x)$ is at least as large as the 'dominant' part of $f(x)$.

It occurred to me today that the phrase "$f(x)$ is asymptotically dominated by $g(x)$" could also mean $f(x) = o(g(x))$, in which case "dominated" is taken to have a more severe connotation, which is why we would require $g(x)$ to grow strictly faster or shrink strictly slower than $f(x)$.

Conclusion

Just be aware of your audience or your source. When clarity is absolutely necessary, use symbols in addition to words.

To answer the OP's specific qestion

Given the "$\sim$" interpretation of "asymptotically equivalent" and the "$O$" interpretation of "asymptotically dominated", it is certainly the case that, if $$f(x) = 5x^3 + x,$$ then $f(x)$ is asymptotically dominated by $x^3$ and asymptotically equivalent to $5x^3$.

The technical definitions we have adopted certainly allow this to happen without a contradiction, perhaps in spite of your intuition based on the the language used.

  • 0
    Thanks. I can see and agree with both statements 1 and 2. But do you agree that it is wrong to say that f(x) is asymptotically dominated by $x^3$? That's the crux of my question, and I apologise if I wasn't clearer before. (Please refer to my comment above.)2012-03-24
  • 1
    No, $f(x)$ is certainly asymptotically dominated by $x^3$. For a more direct proof, consider the ratio $$\left|\frac{f(x)}{x^3}\right| = \left|\frac{5x^3+x}{x^3}\right| = \left|5 + \frac{1}{x^2}\right|.$$ When $x \geq 1$ the above ratio is less than $6$. That is, for $x \geq 1$, $$\left|\frac{f(x)}{x^3}\right| \leq 6,$$ which rearranges to $$|f(x)| \leq 6|x^3|.$$ So, in the definition of big-O, $C=6$, and so you have $f(x) = O(x^3)$. In words, $f(x)$ is asymptotically dominated by $x^3$.2012-03-24
  • 1
    @Ryan, the whole point is that constant multiples don't matter in asymptotics. They're intentionally ignored in the definitions of big-O and big-$\Theta$ when they say "for some constant $C$" or the like.2012-03-24
  • 0
    Hmm. So statements A and B in my original question do not in fact contradict each other?? I understand your explanation above, but I think I've tied myself in knots such that I'm now misunderstanding unidentified facets of the topic!2012-03-24
  • 1
    @Ryan, what exactly does the language "asymptotically equivalent" mean? Can you write this down explicitly? Usually "$f$ is asymptotically equivalent to $g$" means $f = \Theta(g)$, which means that you can find constants $C$ and $D$ such that $|f| \leq C|g|$ and $|g| \leq D|f|$ near your point of interest. (continued...)2012-03-24
  • 1
    @Ryan, So, for your specific case, whether or not you have a $5$ in front of the $x^3$ doesn't matter; it'll just get absorbed into the constants $C$ and $D$, which don't really need to have any properties other than just existing. Writing $|f(x)| \leq C|5x^3|$ really is the same thing as writing $|f(x)| \leq C|x^3|$, since $C$ is more or less arbitrary.2012-03-24
  • 1
    @Ryan, Of course some people use "asymptotically equivalent" to mean that $$\lim_{x \to \infty} \frac{f(x)}{g(x)} = 1,$$ in which case you are right in saying that $f(x)$ is asymptotically equivalent to $5x^3$, not $x^3$. It really just depends on what definition you're using. (But I've seen this definition worded as "asymptotic to" rather than "is asymptotically equivalent to".)2012-03-24
  • 1
    My understanding of asymptotic equivalence is as per: http://www.artofproblemsolving.com/Wiki/index.php/Asymptotic_equivalence . Since $lim(f(x)/5x^3)$ as x approaches infinity equals 1, therefore I conclude Statement B in my original question. And since $lim(f(x)/x^3)$ as x approaches infinity equals 5, I conclude that f(x) is *not* asymptotically equivalent to $x^3$!2012-03-24
  • 1
    @Ryan, in that case, yes, your statement B is correct. Your $f(x)$ is asymptotically equivalent to $5x^3$. Also, you can say that it shares the same order of growth with $x^3$, since $5x^3+x = \Theta(x^3)$. That is, it is asymptotically dominated by and it asymptotically dominates $x^3$.2012-03-24
  • 1
    Well then, problem solved! To avoid future future confusification, I will henceforth use "asymptotic equivalence" only to refer to big-Theta, and sticking to "asymptotic to" to refer to the actual asymptote. So when we say "asymptotically dominates", "asymptotically equivalent", "big O", etc., we are talking about relative growth rates. Antonio, thank you dearly helping to finally de-muddle me!2012-03-24
  • 1
    Glad to help, @Ryan. :)2012-03-24
  • 0
    In fact, I shall abolish the phrase "asymptotically equivalent" from my vocabulary altogether, as I don't like the counter-intuitive idea that a function can be asyptotically dominated by f and yet be asymptotically equivalent to 5f.2012-03-24
  • 0
    @Ryan, I have edited my answer to reflect our discussion here. Please let me know what you think.2012-03-25
  • 0
    I think your revised answer is very clear; hopefully, highlighting the two different definitions of "asymptotic equivalence" in the main answer will render this page more useful than it was! Incidentally, I have just learnt that big-O also has two definitions in usage (refer to the comments under http://math.stackexchange.com/a/124816/21813), possibly opening up another can of worms as to which definition "asymptotic dominance" is a more intuitive fit with...2012-03-27
  • 0
    @Ryan, I saw that post earlier. Madness, pure madness!2012-03-27