1

Is it possible to say something about the order of ratios like $O(1/n^2)/o(1)$ or $O(1/n^2)/O(1/\sqrt{n})$?

rjann
  • 89

2 Answers2

2

You have the property if $f \in O(f_1), g \in O(f_2)$, $fg \in O(f_1 f_2)$.

$O(1/n^2)/o(1)$ can be anything. For example, assume you had the numerator being $\Theta(1/n^2)$ and the denominator being $c/n$. Then, this would go to zero as $1/n$. However, if the denominator went to zero exponentially quickly (i.e. the denominator was something like $e^{-c n}$ for some $c>0$), then this would go infinity exponentially quickly.

Batman
  • 19,390
1

The $O(f(n))$ and similar notations are sets of functions having a certain behavior as $n\to\infty$. We have $O(f(n))=\{g(n):|g(n)|\le Cf(n){\rm\,for\,\, large\,}n\}$, where $C$ denotes some constant. With this definition, $0\in O(f(n))$ for pretty much any $f(n)$, so the expressions you've written don't make sense.

ForgotALot
  • 3,931
  • Thank you @ForgotALot ! Let me ask you one more thing related to this. Assume then that $\theta_n$ is strictly positive and $O(1/\sqrt{n})$. Can you then say something about $O(1/n^2)/\theta_n$? – rjann Feb 12 '16 at 04:10
  • $1/n^a\in O(1/\sqrt{n})$ for $a>1/2$, since in fact $1/n^a\le 1/\sqrt{n}$. Thus for example we can have $\theta_n=1/n^a$ for any such $a>1/2$, and then $O(1/n^2)/\theta_n$ contains functions growing as fast as $1/n^{2-a}$, for example $n$ $(a=3)$, $n^2$, $n^3$, etc. It also, of course, contains functions that go to zero. Thus I find it hard to say anything about $O(1/n^2)/\theta_n$ with the limited information that $\theta_n\in O(1/\sqrt{n})$. – ForgotALot Feb 12 '16 at 04:41