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?

  • 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

4

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
    @Ryan, I saw that post earlier. Madness, pure madness!2012-03-27