I know that $n!$ complexity is higher than exponential complexity and big-O notation says always use the highest growing $n$ term for the naming. But, seeing as this is a factorial to the power of $n$ rather than $n!+x^n$, does that make a difference or would it still simply just be refered to as facorial complexity?
Asked
Active
Viewed 2,906 times
2
-
1$(n!)^n$ grows much faster than $n!$ (just like $n^n$ grows much faster than $n$) so $(n!)^n \not= O(n!)$. Stirlings approximation says that $n! = O[(n/e)^{n+1/2}]$ so $(n!)^n = O[(n/e)^{n^2+n/2}]$. – Winther Sep 06 '15 at 16:26
-
2$\mathcal{O}(n!) \subset \mathcal{O}(n^n)$ – Nigel Overmars Sep 06 '15 at 16:27
-
thanks for the replies. the $n^n$ was an error on my part, I meant to write $x^n$ so I corrected that. – user3129805 Sep 08 '15 at 18:44
1 Answers
1
First mathematically you don't have to only use the highest growing term, it's just one thing we do to shorten it.
If you're really have $O(n!^n)$ then it's definitely larger than both $O(n^n)$ and $O(n!)$, but if you compare $O(n^n)$ and $O(n!)$ they are about the same.
Let's examine the latest closer. $n! = \prod_{j\le n} j \le \prod_{j\le n}n = n^n$, so obviously $n!$ is $O(n^n)$
On the other hand by stirling approxmation we have $n! \approx \sqrt{2\pi n}(n/e)^n$ so $n^n \approx n! e^{n}/\sqrt{2\pi n}$ so it will not be bounded by $n!$. More strictly it's enough to observe that if we consider $n^n/n! = \prod^n_1{n/j} = n\prod^n_2{n/j}$, but since $n\ge j$ in the factors we get $n^n/n! \ge n$, that is $n^n \ge n! n$ (which means there's no constant $K$ such that $n^n \le n!K$ for all $n$).
skyking
- 16,654
-
5Note that $n! = O(n^n)$, but $n^n \not= O(n!)$ so they are not the same. – Winther Sep 06 '15 at 16:30
-
1I find this inequality interesting but could you please explain why that's the case? – user3129805 Sep 08 '15 at 18:45
-
@user3129805 I updated the answer (why $n^n$ is not bounded by $n!$. Maybe that would be explaination you wanted? – skyking Sep 09 '15 at 05:25