1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$?

$\endgroup$
2
  • $\begingroup$ @Ron: I was hoping MathStudent would answer this. $\endgroup$
    – GEdgar
    Jan 28 '15 at 17:30
  • $\begingroup$ Apologies, I misunderstood your intent. $\endgroup$
    – Ron Gordon
    Jan 28 '15 at 17:30
1
$\begingroup$

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

$\endgroup$

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.