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

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.

• just played with the numbers a bit...try k=$\frac{1}{20}$, c=200. check the $n_0$... – DanielY Sep 16 '13 at 5:28
• Can you explain how did you come up with the solution? As much the result helps me if correct, knowing the proof might help me more in long term. – bellpeace Sep 16 '13 at 5:35
• I just played with numbers with 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. I'll write my comment as an answer so you can review it better – DanielY Sep 16 '13 at 5:38

## 2 Answers

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.

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.

• That is true, but I didn't express myself correctly the first time. I need to proof for all k. Sorry again. – bellpeace Sep 16 '13 at 5:45
• so you need small o notation and not big O? – DanielY Sep 16 '13 at 5:46
• @bellpeace I've edited my answer, see if it fits you requirements – DanielY Sep 16 '13 at 5:58
• Ok. To your previous question: I need $(\forall k > 0)\; \lceil\log{n}\rceil! = \Omega(n^k)$. – bellpeace Sep 16 '13 at 5:58
• @bellpeace let me know if there's something unclear – DanielY Sep 16 '13 at 6:18