How to prove anasymptotic equation

32 Views Asked by At

How to prove $$\frac{\varTheta(f(n))}{\varTheta(g(n))}=\varTheta\left(\frac{f(n)}{g(n)}\right),$$and does the property still hold for $O$ and $\Omega$ notations?

Any answers are appreciated!

1

There are 1 best solutions below

1
On

Past some $n_0$,

$$f_0f(n)\le \phi(n)\le f_1f(n), \\g_0g(n)\le \psi(n)\le g_1g(n). $$

Taking the ratio,

$$ \frac{f_0}{g_1}\frac{f(n)}{g(n)}\le\frac{\phi(n)}{\psi(n)}\le\frac{f_1}{g_0}\frac{f(n)}{g(n)}.$$

This establishes the claim and shows that it does not generalize to $O$ nor $\Omega$ as the bounds are crossed (unless you mix $O$ and $\Omega$ appropriately).