856 views
4 votes
4 votes
According to me $n^3$ should be asymptotically greater since $(\log n)!$ is computed like $\log n$ will be a small constant less than $n$ and when I calculate its factorial it will obviously be less than $n^3$.

3 Answers

Best answer
12 votes
12 votes

You should not say "small constant"- "much smaller value than $n$" is correct. But after taking factorial how can we be sure this will remain smaller?

We can take $\log$ for both.

$$\log \left (n^3 \right ) = 3 \cdot \log n \tag{1}\label{1}$$
 

We also know that $\log (x!) = \Theta \Bigl (x \cdot \log (x) \Bigr )$ (Stirling's approximation)

Putting $x = (\log n)$, we get:

$$\log \Bigl ( (\log n) ! \Bigr ) = \Theta \Bigl (\log n \cdot\log (\log n) \Bigr ) \tag{2}\label{2}$$

So, the second one $\eqref{2}$ is asymptotically larger than $\eqref{1}$, as $\log(\log n)$ is asymptotically larger than $3$.

selected by
4 votes
4 votes
$\def\l{(\log_b n)!} \def\n{n^3} \def\L{\,\large}$
The fact that $\l$ grows faster than $\n$ can be somewhat counterintuitive.
So, here's a way you can make it more sensible.

Think of what would happen if instead of having a factorial, we had an exponential. That is, instead of having $\l$, we had $e^{\L \log_b n}$.

Since exponentials and logarithms are inverses of each other, we can simplify it a bit.
$$e^{\,\large \log_b n} = \left (b^{\,\large \log_b e} \right )^{\,\large \log_b n} = \left (b^{\,\large \log_b n} \right )^{\,\large \log_b e} = n^{\,\large \log_b e}$$

This means that is we use an exponential instead of a factorial, we get a polynomail with degree $\log_b e$. Depending on the value of $b$, this degree could be anything between $(-\infty, \infty)$, and thus, even greater than $3$!

So, by using exponentials, we can surpass $n^3$.

But that is not all. We also know that factorials grow faster than exponentials! That is, $x! = \omega(c^x)$. So, if we have a factorial with the $(\log n)$, we are already growing faster than any polynomial $n^c$!

And thus, $\l$ grows faster than $\n$
1 votes
1 votes

For clearer understanding substitute n = 2^m. 

1) (logn) ! changes to m! which can also be written as O(m^m).

and 

2) n^3 changes to 2^3m.

now compare 1) and 2) 

It is visible that 1) grows faster than 2).

Related questions

1 votes
1 votes
0 answers
1
firki lama asked Jan 18, 2017
402 views
Which grows faster when n increases?$I. n^{\frac{1}{3}}<\frac{n}{logn}II. n^{\frac{1}{3}}>\frac{n}{logn}$
3 votes
3 votes
1 answer
3
gate-17 asked Aug 7, 2016
2,808 views
consider the following functions f(n)=log*(log n) , g(n)=log(log* n) relations between these 2 function. please help