5
$\begingroup$

Let $O(n)$ be "Big-O" of $n$ and $o(n)$ be "Small-O" of $n$.

It is a well-known fact that $O(n \log{n}) \subset O(n^{1 + \epsilon})$ for any $\epsilon > 0$. Can we omit the $\epsilon$, and just type $O(n \log{n}) \subset O(n^{1 + o(1)})$?

$\endgroup$
  • $\begingroup$ Are you certain about the meaning of nested Landau symbols? What do you mean by "the tightest bounds" when you give a whole class of bounds? Can there really be a single tightest upper bound (that is not the function itself) when we talk about real functions? $\endgroup$ – Raphael Oct 18 '13 at 20:57
  • $\begingroup$ Sure, it has some disambiguation in notations. But I have seen such notation in research papers. For example, popular paper about algorithms of polynomial factorization over finite fields (people.csail.mit.edu/dmoshkov/courses/codes/…) has that sort of notations. $\endgroup$ – Piotr Semenov Oct 18 '13 at 21:06
  • 2
    $\begingroup$ The question was not whether people use them but whether you are clear about what you/they mean. ;) $\endgroup$ – Raphael Oct 18 '13 at 21:08
6
$\begingroup$

Consider the function $f(n) = n^{1 + \frac{1}{n}}$ which I guess you'd say is in "$O(n^{1 + o(1)})$". I'm not sure you can call it polynomial, though.

Now, compute

$\qquad \displaystyle \lim_{n \to \infty} \frac{n^{1 + \frac{1}{n}}}{n \log n} = 0$,

so you have in fact that $f \in o(n \log n)$. Therefore, functions in this funky class of yours are not even (all) asymptotic upper bounds for $n \log n$.

The difference is that $\varepsilon$ ensures a non-vanishing distance from $n^1$ whereas $o(1)$ means that functions of the form $n^{1 + o(1)}$ in fact converge towards $n \in o(n \log n)$.

$\endgroup$
  • $\begingroup$ Thanks a lot! Can you kindly explain, why authors not just say $O(n \log{n})$ instead of $O(n^{1 + o(1)} \log{n})$? (For example, in paper I mentioned above). It is clear that $O(n \log{n}) = O(n^{1 + o(1)} \log{n})$. $\endgroup$ – Piotr Semenov Oct 18 '13 at 21:17
  • 2
    $\begingroup$ It may happen as result of a longer derivation; then, $o(1)$ is often used as error term, implying that the authors give all contributions of $\Omega(1)$ exactly. For instance, the paper contains $n^{1 + \beta + o(1)}$; saying just $n^{1 + \beta}$ immediately would hide the fact that additional factors had to be shown insignificant; note how different $n^{1 + \beta + O(1)}$ would be! (It's still abuse of notation, but well.) $\endgroup$ – Raphael Oct 18 '13 at 21:44
  • $\begingroup$ I don't get the part "$n^n \in \omega(e^n)$, so $\sqrt[n]{n} \in \mathcal{o}(\log n)$", could you elaborate on that? $\endgroup$ – G. Bach Oct 19 '13 at 1:06
  • $\begingroup$ @Raphael Thanks a lot! Now it makes sense for me. $\endgroup$ – Piotr Semenov Oct 19 '13 at 7:20
  • 1
    $\begingroup$ @PiotrSemenov I just remember another use of such notation: it indicates convergence speed. Compare, for instance, two cases of $f \sim n$: you could show $f = n + \Theta(\log n)$ or $f = n + o(1)$. Both make the same statement about the limit, but different ones about convergence speed. $\endgroup$ – Raphael Oct 19 '13 at 16:27
6
$\begingroup$

Common usage would have $n\log n = n^{1 + o(1)}$. This is a shortcut for $n\log n = n^{1 + f(n)}$ for some function $f(n)$ satisfying $f(n) = o(1)$. In our case, this function is $f(n) = \log \log n / \log n$, which indeed satisfies $f(n) = o(1)$.

$\endgroup$
  • $\begingroup$ It is a good point! As for me, notation like $n^{1 + o(1)}$ is now supposed to be bad because $\frac1{n} \in o(1)$ and $\frac{\log{\log{n}}}{\log{n}} \in o(1)$. Only latter one is proper. So we have no chance to "unzip" shortcut $o(1)$ while having no extra information from the author. I do not like this notation for the complexity analysis needs :) Use it only for convergence analysis as Raphael have mentioned above. $\endgroup$ – Piotr Semenov Oct 20 '13 at 10:23

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.