Are these properties of Big O valid?

Question

I was working through the prime number theorem proof and the following questions arose.

1.) Is $f_1=f_2-\mathcal{O}(x)$ equivalent to $f_1=f_2+\mathcal{O}(x)$ for any two functions $f_1$ and $f_2$.

2.) If I can show that $\log(f_1) = \mathcal{O}(x)$, then $f_1 = e^{\mathcal{O}(x)} = \mathcal{O}(e^x)$

The first seems true because the definition of Big O puts the function in absolute value brackets. i.e. $$f(x) = \mathcal{O}(g(x))$$ If and only if $$ \vert f(x)\vert \leq M g(x) \text{ } \{ x\geq x_o \forall_x, M \in \mathbb{R^+}\}$$ The second is the one I am having a harder time coming to a conclusion about.

Note that $e^{2x} = e^{O(x)}$, but $e^{2x} \neq O(e^x)$. – Fabio Somenzi May 26 '19 at 19:49 — Fabio Somenzi, May 26 '19 at 19:49

score 1 · Accepted Answer · answered May 26 '19 at 21:23

The first property is true: $$f_1=f_2-\mathcal{O}(x)$$ just means $f_2-f_1=\mathcal{O}(x)$, that is, $|f_2-f_1|\le Mx$ "eventually", whereas if $$f_1=f_2+\mathcal{O}(x)$$ then $f_1-f_2=\mathcal{O}(x)$, in other words, $|f_1-f_2|\le Mx$ "eventually".

Since there's an absolute value like you pointed out, they're different.

As for the second property, take Fabio's $e^{2x}=e^{\mathcal{O}(x)}$, and $e^{2x}\neq \mathcal{O}(e^x)$ as a counterexample.

score 1 · Answer 2 · answered May 26 '19 at 21:24

1

The second one is false. That is, $\exp(O(x))\ne O(\exp (x).$

$\log f_1=O(x)$ as $x\to \infty$ means there exists $K>0$ and $ r\in \Bbb R^+$ such that $x>r\implies |\log f_1|\le K|x|.$

That is, $-Kx\le \log f_1\le Kx.$

That is,$ \exp (-Kx)\le f_1\le \exp(Kx).$

Consider the case where $f_1=\exp(999x)$ and $K=999$.

answered May 26 '19 at 21:24

DanielWainfleet

57,985

Always use the definitions. They are the tool set. – DanielWainfleet May 26 '19 at 21:27

Are these properties of Big O valid?

2 Answers2