# Is $(\sqrt{n})!=Θ(\sqrt{n}^{\sqrt{n}})$?

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! asymptotically)

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$$).

• 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) ??
– MJ13
Oct 28 '19 at 9:39
• Right, this is an example for why your kind of reasoning is invalid. Oct 28 '19 at 9:40
• 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 ?
– MJ13
Oct 28 '19 at 9:42
• A simple example is $\log(2^n) = \Theta(\log(3^n))$. Oct 28 '19 at 9:45
• Yuval, would you be against shifting from $= \Theta$ to $\in \Theta$? Oct 28 '19 at 11:23