2
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ You can take a look at Wikipedia's "Landau notation" page: en.wikipedia.org/wiki/… $\endgroup$ – Matt Groff Jan 3 '18 at 4:34
  • 1
    $\begingroup$ The fourth one is wrong, $f\in \Omega (g) \iff \lim_{x\to \infty} \frac{f(x)}{g(x)} > 0$ $\endgroup$ – ultrainstinct Jan 3 '18 at 4:35
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Steven Stadnicki Jan 3 '18 at 4:38
  • 1
    $\begingroup$ 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.$$ $\endgroup$ – Antonio Vargas Jan 3 '18 at 20:16
4
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.