1
$\begingroup$

I would like to express $(\sqrt{n})!$ in terms of $Θ()$ notation.

My approach is the following:

$$(\sqrt{n})!=f(n)\Leftrightarrow$$ $$\log(\sqrt{n})!=\log(f(n))$$

Now from Stirling's approximation we get: $$Θ(\sqrt{n}\log(\sqrt{n})=\log(f(n))\Leftrightarrow$$ $$f(n)=Θ(\sqrt{n}^{\sqrt{n}})$$

So, $$(\sqrt{n})!=Θ(\sqrt{n}^{\sqrt{n}})$$

Is this approach correct? I am a bit confused since I used $\log$ equality to prove this and in some cases this doesn't work correctly.

For example, if we get $n!$ and $n^{n}$ we observe that $Θ(\log(n!))=Θ(\log(n^{n})$ .

However we know that $n!=o(n^{n})$ (which means that $n!<n^{n}$ asymptotically)

$\endgroup$
3
$\begingroup$

Stirling's approximation states that $$ n! \sim \sqrt{2\pi n} (n/e)^n = \Theta(\sqrt{n} (n/e)^n). $$ Therefore $\sqrt{n}! = \Theta(n^{1/4} (\sqrt{n}/e)^{\sqrt{n}})$. In particular, $\sqrt{n}! = o(\sqrt{n}^{\sqrt{n}})$.

Note also that if all you want is to express $\sqrt{n}!$ in big Theta notation, you can just write $\sqrt{n}! = \Theta(\sqrt{n}!)$.

If $\log f(n) = \Theta(\log g(n))$ then it doesn't follow that $f(n) = \Theta(g(n))$. For example, $\log (a^n) = \Theta(\log (b^n))$ for all $a,b > 1$, but $a^n$ is not $\Theta(b^n)$ (unless $a = b$).

$\endgroup$
8
  • $\begingroup$ So, If I get it right, it's wrong to use $\log$ equality to express the big Thera notation and using Stirling's approximation I end up with: $\sqrt{n}! = \Theta(n^{1/4} (\sqrt{n}/e)^{\sqrt{n}})$ (which is a different result) ?? $\endgroup$ – MJ13 Oct 28 '19 at 9:39
  • $\begingroup$ Right, this is an example for why your kind of reasoning is invalid. $\endgroup$ – Yuval Filmus Oct 28 '19 at 9:40
  • $\begingroup$ Yeah I see. And that's why if we have $n!$ and $n^{n}$ and we want to compare them asymptotically then getting $Θ(\log(n!))=Θ(\log(n^{n}))$ doesn't help us somehow , right ? $\endgroup$ – MJ13 Oct 28 '19 at 9:42
  • $\begingroup$ A simple example is $\log(2^n) = \Theta(\log(3^n))$. $\endgroup$ – Yuval Filmus Oct 28 '19 at 9:45
  • $\begingroup$ Yuval, would you be against shifting from $= \Theta$ to $\in \Theta$? $\endgroup$ – D. Ben Knoble Oct 28 '19 at 11:23

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.