patternMinor
Is $\log{n}$ bounded from above by $n^{o(1)}$?
Viewed 0 times
boundedfromabovelog
Problem
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)})$?
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)})$?
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#16210, answer score: 6
Revisions (0)
No revisions yet.