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)$.

  • $\begingroup$ Technically, 0 is O(0). But otherwise yes. $\endgroup$ – Ian Aug 26 '17 at 14:47
  • 1
    $\begingroup$ Yes, although you should write $|x_n|\leq C|\alpha_n$| as $\alpha_n$ may be $0$ for some $n.$ $\endgroup$ – DanielWainfleet Aug 26 '17 at 14:54
  • $\begingroup$ a less math talk about it : rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation $\endgroup$ – user451844 Aug 26 '17 at 14:56
  • $\begingroup$ 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. $\endgroup$ – LutzL Aug 26 '17 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.