3
$\begingroup$

Seeing the title, you will probably like to give your explanation as

$n!=n\times (n-1)\times (n-2)\times (n-3)\times\cdots\times 1$

where as

$n^n$ = $n\times n \times n\times n \times\cdots\times n$ $\text{($n$-times)}$

but consider one thing: if we do $\log(n!)$ then it comes out to be $O(n\log n)$.

enter image description here

On the other hand, if we do $\log(n^n)$ it also comes out to be $O(n\log n)$. So, aren't they equal asymptotically?

$\endgroup$
  • 1
    $\begingroup$ Yes, both $\log n!$ and $\log n^n$ are equal asymptotically, but not $n!$ and $n^n$. $\endgroup$ – zdm Nov 25 '19 at 18:11
8
$\begingroup$

The core source of your confusion is that you have assumed that the asymptotic behavior of functions is closed under taking $\log$, which is false. There are countless examples, take: $$f(n)=n^{100}, \quad g(n)=n$$ If you take their logarithm they become: $$\log f(n) = 100 \log n,\quad \log g(n) = \log n $$ So their logarithms are both linear in $\log n$, while it's obvious they do not have a similar growth rate. Another example can be: $$f(n)=\exp(2 n), \quad g(n)=\exp(n)$$ and their logarithms are: $$\log f(n) = 2n, \log g(n) = n$$ You can see that $f(n) = g(n)^2$ and it has faster growth rate, but both their logarithms are linear in $n$. The intuitive reason is that, when you compare $\log f(n)$ and $\log g(n)$, you are basically comparing their exponents. Showing that the exponents of two functions have a similar growth rate is not the same as showing that the functions have the same growth rate.

In case you are wondering, the reversed direction would actually hold most of the time: If $\log f(n)$ grows faster than $\log g(n)$, and $g(n)=\Omega(1)$, then $f(n)$ grows faster than $g(n)$, and the condition $g(n)=\Omega(1)$ prevents cases like $f(n) = \exp(1/n), g(n) = \exp(1/n^2)$.

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

The first part is right. But you have a wrong conclusion! If $g(n) = \Theta(f(n))$, you cannot say for $every$ function $h(n)$, $h(g(n)) = \Theta(h(f(n))$.

For the case, we know that $\log(n!) = \Theta(n\log(n))$, but you can not conclude that it is also true if we apply $h(n) = e^n$ over the functions. In your case, intuitively, the main difference in $\log$ cases and exponential cases is we sum limits in $\log$ cases and multiply limits in the exponential case!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ h(g(n))=Θ(h(f(n)) I am not saying this, I am just concerned about g(n)=Θ(f(n)) say we have a function for(int i=0; i<n;i++) {}; its complexity is O(n) and similarly for any other recursive function like T(n)=T(n-1)+c we also have a complexity of O(n) In this case we can say that these 2 algorithms are assymptoticaly same as one another, but why not for my example of factorial and exponentiation? $\endgroup$ – Turing101 Nov 25 '19 at 12:10
  • $\begingroup$ @HIRAKMONDAL indeed using $O$ notation here definitely wrong! $1$ is in $O(n)$ and $n$ is $O(n)$. Definitely you cannot conclude that $1$ and $n$ are asymptotically the same! $\endgroup$ – OmG Nov 25 '19 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.