0

I cannot really understand what is right: $$n^{\mathcal{O}(1)} = \mathcal{O}(n^{logn})$$ or $$n^{\mathcal{O}(1)} = \mathcal{o}(n^{logn})$$

I know that Little-oh notation means

For every choice of a constant k > 0, you can find a constant a such that the inequality f(x) < k g(x) holds for all x > a.

and Big-Oh

For at least one choice of a constant k > 0, you can find a constant a such that the inequality f(x) < k g(x) holds for all x > a.

But, it is not clear for me haiving $n^{\mathcal{O}(1)}$ and $(n^{logn})$ because whether $n^{\mathcal{O}(1)} < n^{logn}$ or $n^{\mathcal{O}(1)} > n^{logn}$ only matters on $n$ itself and the actual exponent of $n$.

Like $2^{1000} > 2^{log2}$ but as n grows $n^{logn}$ will become larger. Etc. So it may be that $$n^{\mathcal{O}(1)} < n^{logn}$$ or $$n^{\mathcal{O}(1)} > n^{logn}$$ or $$n^{\mathcal{O}(1)} = n^{logn}$$

But $n^{logn}$ grows asymptotically faster.

So, are we dealing with big or little oh?

YanyongXu
  • 81
  • Strictly speaking neither is correct, because $n^{O(1)}$, etc. represent sets of functions, and none of them are equivalent as sets. – Steven Stadnicki Oct 05 '15 at 03:57
  • I think the notation f(x) = O(n) technically means f(x) is an element of O(n) (it's bad notation imo, but people still use it). I suppose then that the question wouldn't be meaningful if n^O(1) was meant to represent a set. – nivekgnay Oct 05 '15 at 04:20
  • @nivekgnay There's no way to really properly think of $n^{O(1)}$ as anything but a set. And one can certainly ask meaningful questions along these lines - for instance, as sets, it's the case that $O(n) = O(2n)$. Here it would be correct to say that both $n^{O(1)}\subset O(n^{\log(n)})$ and $n^{O(1)}\subset o(n^{\log(n)})$. – Steven Stadnicki Oct 05 '15 at 04:56
  • I think you have a lot of good points. What I meant to say is that given the poor notation that f(x) = O(n) actually means $f(x) \in O(n)$, the question wouldn't have been meaningful. – nivekgnay Oct 05 '15 at 05:04
  • @StevenStadnicki https://en.wikipedia.org/wiki/Big_O_notation#Equals_sign – nivekgnay Oct 05 '15 at 05:17

1 Answers1

0

$n^{(O(1))}$ is actually both $O(n^{log(n)})$ and $o(n^{log(n)})$. Note that $o(n^{log(n)})$ is the stronger upper bound. In other words, $f(x) = o(n^{log(n)}) \implies f(x) = O(n^{log(n)})$.

Note that any function in $O(1)$ must be a constant. Denote that constant by $c$. We want to show that for any choice of $k > 0$, we can find a constant $a$ such that $n^c < k*n^{log(n)}$ for all $n > a$. Note that there exists a constant $e$ such that $n^e > 1/k$ for all k as long as $n>1$, since k is a constant. Consider selecting an $a$ such that $log(a) > c + e$. Then whenever $n > a$, $k*n^{log(n)} > k*n^{c+e} > n^c$. Thus, $n^{O(1)} = o(n^{log(n)})$, and it follows that $n^{O(1)} = O(n^{log(n)})$.

When proving these things, it is important to realize that you are trying to compare functions when the inputs get arbitrarily large. Sure, $2^{1000} > 2^{log(2)}$, but this does not say much about the relative growth rates of the function in general. The definitions of big-O and little-O seek to reach this sort of generalization when it comes to function growth comparisons.

nivekgnay
  • 653