What is the big-$O$ size of a function like $\frac{n^n}{2^n}$?

55 Views Asked by At

So, it is clear that factorial (i.e., $O(n!) = O(n^n)$) growth rate outpaces that of exponential (i.e., $O(c^n)$ for a constant $c$).

However, what happens when we divide the two?

That is to say, what is the asymptotic representation of a function like $f(n)=\frac{n^n}{2^n}$?

When multiplying terms, of course you take the "most influential" power, e.g. a function $f(n)=2^n 17n^{100} 2n^6 n^3$ would belong to the class $O(2^n)$, but how does this work when dividing functions?

1

There are 1 best solutions below

1
On

Your premise is incorrect: $2^n n^{100} n^6 n^3$ is not $O(2^n)$. You do not take the "most influential power". Whoever told you that is not using $O$-notation in the way it is used in mathematics. In my experience some people get the wrong idea of what $O$-notation means: it is an upper bound with constant factors suppressed. When I say $a_n = O(n^3)$, I am not saying $a_n$ "grows like" $n^3$, but only that it grows at most like $Kn^3$ for a constant $K$. That $O$-estimate could be really wasteful: the sequence $a_n = 4n+5$ is $O(n^3)$. There is no rule that $O$-estimates can't be terrible. But they have to be correct, matching the actual meaning of $O$-notation.

By definition, a sequence is $O(2^n)$ when it grows for large $n$ no faster than a constant times $2^n$. If $a_n \leq 14343 \cdot 2^n$ then $a_n = O(2^n)$. If $a_n \leq n 2^n$ then without further information we can not say $a_n = O(2^n)$. The sequences $a_n = 2^n/7$ and $a_n = \sqrt{n}2^n$ are both $\leq n 2^n$, with the first sequence being $O(2^n)$ and the second sequence not being $O(2^n)$.

You ask what the asymptotic representation of $n^n/2^n$ is. Are you asking for an asymptotic estimate or a $O$-estimate? Those are not the same thing (maybe you're abusing $O$-notation). There is no universal answer to what an estimate is. You can always be stupid and say the estimate of something is itself: $n^n/2^n \sim n^n/2^n$ and $n^n/2^n = O(n^n/2^n)$. Or, since $n^n/2^n < n^n$ for $n \geq 1$, you could say $n^n/2^n = O(n^n)$.