How can I prove that $\log^k(n) = O(n^\epsilon)$?

Solution 1:

By definition we have

$$\log^k(n) = n^\epsilon\cdot \frac{\log^k(n)}{n^\epsilon}$$

with

$$\frac{\log^k(n)}{n^\epsilon}\to 0$$

(refer to Evaluation $\lim_{n\to \infty}\frac{{\log^k n}}{n^{\epsilon}}$)

therefore

$$\log^k(n) = o(n^\epsilon)$$

Solution 2:

Consider $\;\log\biggl(\dfrac{\log^kn}{n^ε}\biggr)$: $$\log\biggl(\dfrac{\log^kn}{n^ε}\biggr)=k\log(\log n)-ε\log n=-ε\log n\biggl(1-\frac kε\underbrace{\frac{\log(\log n)}{\log n}}_{\stackrel{\downarrow}{0}}\biggr)$$ so the log tends to $-\infty$ when $n$ tends to $\infty$, i.e. $$\lim_{n\to\infty}\dfrac{\log^kn}{n^ε}=0\iff\log^kn=o(n^ε),$$ and a fortiori, it is $\:O(n^ε)$.

Solution 3:

It is well known that $\log (m)<m$ for all $m>0$. Taking $m=n^{\epsilon/k}$ gives $$\dfrac{\epsilon}{k} \log(n)<n^{\dfrac{\epsilon}{k}}$$ and manipulating this equation gives $$\log^k (n)<\left(\frac{k}{\epsilon} \right)^kn^\epsilon. $$

Solution 4:

Here we'll try to come up with an explicit lower bound for $n$ instead of using limits. We need to solve $\log^k(n) \leq n^\epsilon$ (Here I assume the big-Oh constant $c=1$). Assuming $n$ large, in particular $n > 1$ we can rewrite $n = e^m$. for some $m > 0$. This gives us to solve: $$ \log^k(n) \leq n^\epsilon \Leftrightarrow m^k \leq e^{\epsilon m} $$ Now for $\epsilon, m > 0$, we have $$ e^{\epsilon m} = \sum_{i=0}^\infty \frac{(\epsilon m)^i}{i!} > \frac{(\epsilon m)^{k+1}}{(k+1)!} $$ This gives us the implication: $$ m^k \leq \frac{(\epsilon m)^{k+1}}{(k+1)!} \implies m^k \leq e^{\epsilon m} $$ Hence if we manage to solve for $m$ the LHS of the implication, we will have found a satisfying $m$ for the RHS and we will be done. Let's try: $$ m^k \leq \frac{(\epsilon m)^{k+1}}{(k+1)!} = \frac{\epsilon^{k+1}}{(k+1)!} m^{k+1}\Leftrightarrow \\ 1 \leq \frac{\epsilon^{k+1}}{(k+1)!} m \Leftrightarrow \\ \frac{(k+1)!}{\epsilon^{k+1}} \leq m $$ By our definition we have $m = \log(n)$, therefore we have the explicit (and awfully loose) bound:

$$ n \geq \exp\left(\frac{(k+1)!}{\epsilon^{k+1}}\right) \implies \log^k(n) \leq n^\epsilon $$

(Note that I assume for simplicity that $c=1$. But it really doesn't matter. This shows that this proof can hold for any $c$, which means that we have the stronger result: $\log^k(n) = o(n^\epsilon)$)

Solution 5:

Propositions 1. Function $f(x)=\frac{x^{\varepsilon}}{\ln^k{x}}$ is ascending for large $x>0$.

Because $$f'(x)=\frac{x^{\varepsilon-1} (\varepsilon \ln^k{x}-k)}{\ln^{k+1}{x}}>0 \iff \varepsilon \ln^k{x}-k>0 \iff x> e^{\sqrt[k]{\frac{k}{\varepsilon}}}$$

Propositions 2. $\lim\limits_{x\rightarrow \infty}f(x) \rightarrow \infty$

If we assume it is bounded by a large $\alpha>0, \forall x>1$ and we know $\ln{x}$ is ascending $$\frac{x^{\varepsilon}}{\ln^k{x}} < \alpha \iff 1<x^{\varepsilon}< \alpha \ln^k{x} \iff \color{red}{0}<\varepsilon<\frac{\ln{\alpha}}{\ln{x}}+\frac{k\ln{\ln{x}}}{\ln{x}}\rightarrow \color{red}{0}, x\rightarrow\infty$$ which is a contradiction of $\varepsilon>0$. So, $f(x)$ is increasing and has no upper bound.

As a result: $$\lim\limits_{n\rightarrow\infty}\frac{n^{\varepsilon}}{\ln^k{n}}\rightarrow\infty \iff \lim\limits_{n\rightarrow\infty}\frac{\ln^k{n}}{n^{\varepsilon}}=0 \iff \ln^k{n}=o\left(n^{\varepsilon}\right)$$