0

I’m interested in what operations preserve asymptotic relationships.

For example, I can prove that if $f=o(g)$ (as $x\to\infty$), then $a^f=O(b^g)$, for any bases $a,b>1$.

But I think that’s the best we can say: I don’t think we can improve the big-oh in the conclusion to a little-oh. Yet I can’t find a counterexample.

Is that right? If so, what’s a good counterxample?

More generally, what’s some good intuition about how asymptotic relationships change when we apply an operator besides exponentiation?

user1435
  • 21

3 Answers3

2

Example A

$2x = O(x)$ as $x\to\infty$, but of course $e^{2x}$ is not $O(e^x)$.

Example B

$1/x^2 = o(1/x)$ as $x\to\infty$, but $e^{1/x^2} \to 1$ and $e^{1/x} \to 1$ so $e^{1/x^2}$ is not $o(e^{1/x})$.

Example C, $a \ne b$

$x+\sqrt{x} = \Theta(x)$ but $2^{x+\sqrt{x}} = o(3^x)$

GEdgar
  • 111,679
0

Hint: $a^f/b^g=b^{\log_b(a)f}/b^g=b^{\log_b(a)f-g}$.

More generally, it depends what sort of operation you apply. Applying the exponential is very different from applying the logarithm or $\arctan$.

tomasz
  • 35,474
  • How does the comment help? I see that if $f$ is little oh of $g$, then the exponent in your last expression is eventually negative, thus the whole expression is eventually less than $1$. But I don’t see that the exponent in your last expression has to tend to $-\infty$, say. So not sure what your hint is supposed to be telling me. – user1435 Sep 09 '19 at 23:41
0

You might want to take a peek at Joel Spencer's "Asymptopia" (AMS, 2014), an in-depth discussion of matters asymptotical. Or take a look at Hildebrand's Short Course on Asymptotics.

vonbrand
  • 27,812