2

This is more for clarification than anything else, in my text we define:

Definition: We say $x_n = \mathcal{O}(\alpha_n)$ if there are constants $C$ and $n_0$ such that $|x_n| \leq C|\alpha_n|$ when $n \geq n_0$.

Am I right in saying that the ratio $\dfrac{|x_n|}{| \alpha_n |} \leq C$, where $\alpha_n \neq 0$ is bounded as $n\to\infty$ for $x_n = \mathcal{O}(\alpha_n)$ as a necessary condition.

So that if $$\lim_{n\to\infty} \dfrac{ |x_n|}{|\alpha_n|} = \infty$$ then $x_n \neq \mathcal{O}(\alpha_n)$.

Dragonite
  • 2,388
  • Technically, 0 is O(0). But otherwise yes. – Ian Aug 26 '17 at 14:47
  • 1
    Yes, although you should write $|x_n|\leq C|\alpha_n$| as $\alpha_n$ may be $0$ for some $n.$ – DanielWainfleet Aug 26 '17 at 14:54
  • a less math talk about it : https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ –  Aug 26 '17 at 14:56
  • There are many cases in between where such a limit does not exist (even in the form of divergence to $∞$), while a classification into $O(α_n)$ or not is still possible. – Lutz Lehmann Aug 26 '17 at 17:04

0 Answers0