Proof of Complexity

Question

If I want to prove that $f=O(g)$ for $f(x)=x^{1/2}$ and $g(x)=x^{2/3}$, is it sufficient to say that $\lim_{x \to \infty}f(x)/g(x)=0$? I'm not sure if this is a convincing enough argument or more elaboration is required.

Answer 1

That is absolutely true -- always. Why?

If $f(x)\rightarrow g(x)\rightarrow0$ as $x\rightarrow\infty$, then there is some constant $N>0$ such that $\lvert f(x)/g(x)\rvert\leq 1$ for all $x\geq N$. But this means that for all $x\geq N$, we have $\lvert f(x)\rvert\leq \lvert g(x)\rvert$; under the (usual) assumption that $g\geq 0$, this implies that for $x\geq N$ we have $\lvert f(x)\rvert\leq g(x)$, and hence $f(x)=O(g(x))$ as $x\rightarrow\infty$.