# Is this cheat sheet over big-$O$ and related notations accurate?

When familiarizing myself with big-$O$ and similar notations, I found this cheat sheet (which I took the liberty of transcribing):

$$\begin{array}{c|c} \text{big-O notation} & \text{limit definition} \\[2ex] \hline f\in o(g) & \displaystyle\lim_{x\to\infty}\frac{f(x)}{g(x)}=0 \\[2ex] f\in O(g) & \displaystyle\lim_{x\to\infty}\frac{f(x)}{g(x)}\lt\infty \\[2ex] f\in \Theta(g) & \displaystyle\lim_{x\to\infty}\frac{f(x)}{g(x)}\in\Bbb{R}_{\ge0} \\[2ex] f\in\Omega(g) & \displaystyle\lim_{x\to\infty}\frac{f(x)}{g(x)}\lt\infty \\[2ex] f\in\omega(g) & \displaystyle\lim_{x\to\infty}\frac{f(x)}{g(x)}=\infty \\[2ex] \end{array}$$

I am not at all familiar with notations like this for asymptotic behavior, so my questions are pretty straight-forward and simple:

• Is any of the quoted material inaccurate? If so, what?
• Are there any ‘caveats’ with asymptotic notation of which students should be wary? Perhaps something that might easily be misunderstood on the superficial level?
• You can take a look at Wikipedia's "Landau notation" page: en.wikipedia.org/wiki/… – Matt Groff Jan 3 '18 at 4:34
• The fourth one is wrong, $f\in \Omega (g) \iff \lim_{x\to \infty} \frac{f(x)}{g(x)} > 0$ – ultrainstinct Jan 3 '18 at 4:35
• The fourth one should be $f\in\Omega(g)\Leftrightarrow\lim_{x\to\infty}\frac{g(x)}{f(x)}\lt\infty$; i.e., $f\in\Omega(g)\Leftrightarrow g\in O(f)$. – Steven Stadnicki Jan 3 '18 at 4:38
• I'd also note that these definitions basically assume that $f,g > 0$. You can generalize these notations to include functions which take negative values or even complex values. For example, $$f \in O(g) \iff |f(x)| \leq C|g(x)| \iff \limsup \left|\frac{f(x)}{g(x)}\right| < \infty.$$ – Antonio Vargas Jan 3 '18 at 20:16

There's one major problem that infests several of these: the cheat-sheet effectively requires the various limits in question to exist, but that's not strictly a necessity for some of these definitions. For instance, consider $f(x)=x(1+\{x\})$, where $\{x\}$ denotes the factional part of $x$. Then $f(x)\in O(x)$ and in fact $f(x)\in\Theta(x)$, but the limit $\lim\limits_{x\to\infty}\frac{f(x)}{x}$ doesn't exist; it vacillates between $1$ and $2$. Also, as noted in the comments, the definition of $\Omega()$ is wrong; it "should be" $\lim\limits_{x\to\infty}\frac{g(x)}{f(x)}\lt\infty$, although that's also wrong for the same reason that the definition of $O()$ is wrong; better would be just to say that $f\in\Omega(g)\Longleftrightarrow g\in O(f)$.