1

Is $\lceil{\lg n}\rceil!$ polynomially bounded?

I've tried using Stirlings Approximation, and I get that $\lceil{\lg n}\rceil! \approx \sqrt{2\pi}\lceil{\lg n}\rceil^{1/2}\lceil{\lg n}\rceil^{\lceil \lg{n} \rceil}e^{-\lceil \lg{n} \rceil}$

But I'm stuck here because I'm not sure what to do with all of the ceilings...

One idea I had was to just pretend lg n is an integer...in which case I've got something like than $\frac{{\lg n}^{\lg n + 1/2}}{n}$, which then I believe is polynomially bounded since if I took logs from here, I would have something $O(\log(n)^2)$...but can I do this?

So my question is, why is it justified to do that...or if not, how do I solve the problem?

MathStudent
  • 1,352
  • 11
  • 22

2 Answers2

2

You need to decide whether $(\log n)^{\log n}$ is polynomially bounded or not.

For example, can you prove $$ (\log n)^{\log n} < n^5 $$ for large enough $n$?

GEdgar
  • 111,679
1

The ceilings don't matter; $\lceil f(n) \rceil \leq f(n)+1 \leq 2 f(n)$ provided $f(n) \geq 1$. So up to a constant factor you are dealing with $\log(n)^{1/2} \log(n)^{\log(n)} (1/n)$. Here's a hint on how to manage that:

$$\log(n)^{\log(n)} = \exp ( \log(n) \log(\log(n))) = n^{\log(\log(n))}$$

Ian
  • 101,645