Basic Big-O Question

Question

I had 2 very small queries regarding Big-O notation:

If $f(x) = O(g(x))$, then for any constant a, is it the case that $a^{f(x)} = O(a^{g(x)})$?
If $f(x) = O(g(x))$ and $h(x) = O(i(x))$, then does $h(x)^{f(x)} = O(i(x)^{g(x)})$?

Any help would be much appreciated!

Consider the counterexample $f(x)=x$, $g(x)=2x$, $h(x)=i(x)=a=2$. — Mostafa Ayaz, Jan 27 '23 at 13:35
Suppose $2^x = O(2^{2x})$. Then exists $C>0$ such that $C\cdot 2^x > 2^{2x}=4^x$ for all $x>0$. It follows that $C > 2^x$, a contradiction. — Dima Chubarov, Jan 27 '23 at 14:27
It is the other way around: $ 2^x\leq C 2^{2x}$ as $x$ goes to $\infty$. — Caio, Jan 27 '23 at 14:34

score 0 · Accepted Answer · answered Jan 27 '23 at 14:41

For the first one, consider for example $f(x)=\ln x$, $g(x)=x$ and $a=\frac{1}{2}$. Then \begin{align} \ln x=O(x) \end{align} as $x\to\infty$. But it is not true that \begin{align} \frac{1}{2^{\ln x}}=O\bigg(\frac{1}{2^x}\bigg) \end{align} as $x\to\infty$.

For the second, take $f(x)=1,\forall x$ and $g(x)=x$. Also $h(x)=\frac{1}{x^2}$ and $i(x)=\frac{1}{x}$. Then we have \begin{align} h(x)^{f(x)}&=\frac{1}{x^2};\\ i(x)^{g(x)}&=\frac{1}{x^x} \end{align} But $\frac{1}{x^x}=O(\frac{1}{x^2})$, as $x\to\infty$.

Basic Big-O Question

1 Answers1