Substitution in Big-O notation

493 Views Asked by At

If I have two statements, one of the form $f\sim g$ and the other of the form $f=O(g)$ of which the definitions are: $$f\sim g\implies\lim_{x \to \infty}\left|\frac{f(x)}{g(x)}\right|=1 \quad\quad\quad f=O(g) \implies \lim_{x \to \infty}\left|\frac{f(x)}{g(x)}\right|=c $$ where c is a constant, can I substitute one into another without having to substitute the whole limit?

For example, say $x^2 \sim \sqrt{2x}$ and then I want to show whether $x^2=O(x^{x+\frac{1}{2}})$, would I be able to express this as $$\lim_{x \to \infty}\left|\frac{x^2}{x^{x+\frac{1}{2}}}\right|=\lim_{x \to \infty}\left|\frac{\sqrt{2x}}{x^{x+\frac{1}{2}}}\right|=c$$ or would I have to find a way to fit the $\left|\frac{x^2}{\sqrt{2x}}\right|=1$ into the limit?

1

There are 1 best solutions below

0
On BEST ANSWER

Given that $f\sim g$ and $f=O(h)$,

$$\lim_{x\to\infty}\left|\frac{f(x)}{h(x)}\right|=\lim_{x\to\infty}\left|\frac{f(x)}{h(x)}\right|\cdot\lim_{x\to\infty}\left|\frac{g(x)}{f(x)}\right|=\lim_{x\to\infty}\left|\frac{f(x)}{h(x)}\frac{g(x)}{f(x)}\right|=\lim_{x\to\infty}\left|\frac{g(x)}{h(x)}\right|$$

To reach this conclusion, you would need to show the following:

  1. $f\sim g\iff g\sim f$
  2. $\lim\limits_{x\to\infty}a(x)\cdot\lim\limits_{x\to\infty} b(x)=\lim\limits_{x\to\infty}a(x)b(x)$
  3. $|a||b|=|ab|$
  4. Beyond some point, $f,g,h$ are never $0$.

Let me know if you spot any mistakes, or if this does not answer your question.