Inequality $C\lceil\log{n}\rceil! \geq n^k$

Question

I've been struggling to prove there exist $C$ for $n, n_{0}, \forall k >0 \in \mathbb{R}$ such that $\forall n > n_{0}$:

\begin{equation}C\lceil\log{n}\rceil! \geq n^k\end{equation}

As you might guess, this is from algorithm analysis. Since $n \in \mathbb{R}$, I've tried using a substitution $n = 2^{x}$ to get rid of the logarithm, but was not able to come up with $C$ anyway. Any help appreciated, but proof method would be great.

Answer 1

Let $C=1$. We show that after a while, $\lceil \log n\rceil! \ge n^k$.

Let $m=\lceil \log n\rceil$. Equivalently, by taking logarithms, we see that we want to show that after a while, $\log (m!)\gt k\log n$.

Note that $$\log m!=\log 1+\log 2+\log 3+\cdots +\log m.\tag{1}.$$ The right-hand side of (1) is greater than $$\int_1^m \log x\,dx=m\log m-m +1.$$ Since $m \gt \log n$, we obtain $$\log(m!)\gt (\log n)(\log\log n)-\log n+1\gt (\log n)(\log\log n-1).\tag{2}$$

We need to show that after a while, the right-hand side of (2) is greater than $k\log n$.

That will be the case if $\log\log n-1\gt k$. That gives for $n_0$ the possibly very large number $\exp(\exp(k+1))$.

Remark: We found a quite crude lower bound for $\log(m!)$. Please see the Stirling Approximation for much sharper results.

Answer 2

I just played with the numbers using common sense: $logn$ is a much smaller function than $n^k$ so I needed to enlarge the former and reduce the latter, which i've done with a big $c$ and a really small $k$.

What I've come up with is:

$k = \frac{1}{20}$ $c = 200$

I'll leave you deal with the $n_0$, let me know if you need further help

EDIT DUE TO NEW INSTRUCTION:

You said you need the inequality to apply for a certain C for all k and for all n>$n_0$.

According to what I've learnt, it means that we need to find a C that: $\lim_{n->\infty}\frac{n^k}{C(logn)!} = 0$

Again, played with numbers:

Take $C = 1$, for every k you see it applies, check the $n_0$ you need and you're done.