2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ just played with the numbers a bit...try k=$\frac{1}{20}$, c=200. check the $n_0$... $\endgroup$ – DanielY Sep 16 '13 at 5:28
  • $\begingroup$ 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. $\endgroup$ – bellpeace Sep 16 '13 at 5:35
  • $\begingroup$ 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 $\endgroup$ – DanielY Sep 16 '13 at 5:38
2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

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

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.