Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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)$? –  Antonio Vargas Mar 24 '12 at 18:41
    
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). –  user20266 Mar 24 '12 at 18:45
    
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? –  Ryan Mar 24 '12 at 18:53
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
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$. –  Antonio Vargas Mar 24 '12 at 19:04
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. –  Antonio Vargas Mar 24 '12 at 19:12
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...) –  Antonio Vargas Mar 24 '12 at 19:36
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. –  Antonio Vargas Mar 24 '12 at 19:36
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".) –  Antonio Vargas Mar 24 '12 at 19:41
show 10 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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