Prove that $\log_{2}(n) = O(n^{1-\epsilon})$ for any $0 \leq \epsilon < 1$

Question

We assume that $n>0$. I would like to get some feedback on my proof of this statement.

When we want to show that $f(n) = O(g(n))$, we need to find some positive constants $c, n_{0}$ such that for every $n \geq n_{0}$ the following holds: $f(n) \leq cg(n)$. Here $f(n) = \log_{2}(n)$ and $g(n) = n^{1-\epsilon}$, so we want to find some positive constants $c,n_{0}$ such that $\log_{2}n \leq cn^{1-\epsilon}$ for every $n\geq n_{0}$.

For $\log_{2}n \leq cn^{1-\epsilon}$ to be true, then $\log_{2}(\log_{2}n) \leq \log_{2}(cn^{1-\epsilon})$ must be true. Doing the math from there we have:

$\log_{2}(\log_{2}n) \leq \log_{2}(c) + \log_{2}(n^{1-\epsilon}) = \log_{2}(c) + (1-\epsilon)\log_{2}(n)$

because $n$ is positive, $\log_{2}(n)$ will also be positive so we have

$\log_{2}(\log_{2}n) \leq (\log_{2}(c) + (1-\epsilon))\log_{2}(n)$

now at this point, someone could suggest that all we need to do is find a constant $c$ such that $(\log_{2}(c) + (1-\epsilon)) \geq 1$. This happens when $c = 2^{\epsilon}$.

However shouldn't we also prove that $\log_{2}(\log_{2}n) \leq \log_{2}(n)$ for every $n>n_{0}$? I have seen many proofs where they just pick an $n_{0}$ without formally going over the argument. My claim is that we can pick $n_{0} = 4$. So now we need to prove that $\log_{2}(\log_{2}n) \leq \log_{2}(n)$ for every $n>4$ and together with the constant that we picked above this will complete the proof of the original statement.

Let $h(n) = \log_{2}(\log_{2}n) - \log_{2}(n)$. We have that $\frac{\partial h}{\partial n} = \frac{1-\ln(n)}{n\ln(2)\ln(n)}$. This derivative becomes 0 when $n = e$. Since $h(4) = -1 < 0$ this means that $h(n) < 0$ for every $n>=4$. So $\log_{2}(\log_{2}n) \leq \log_{2}(n)$ for every $n>=4$, which means that we can pick $n_{0} = 4$.

Answer 1

You made one small mistake in the proof.

As we are working backwards from the definition, we have to take care that the deductions we make are valid when applied backwards. This is tricky when order relations are involved!

Concretely, you are saying that since $$\log_2(\log_2 n)\le\log_2(c)+(1-\epsilon)\log_2(n) \tag{1}$$ and $$\log_2(c) \le \log_2(c)\log_2(n) \tag{2}$$ then it must be the case that $$\log_2(\log_2 n)\le\log_2(c)+(1-\epsilon)\log_2(n)\le\log_2(c)\log_2(n)+(1-\epsilon)\log_2(n)=(\log_2 c + (1- \epsilon))\log_2 n\tag{3}$$.

This is of course literally valid, but we are not interested in having (1) as a premise, but rather as a conclusion!

---

I want to suggest as an alternative way of proving the result: to study the asymptotic behavior of the quotient $\frac{\log_2(n)}{n^{1-\epsilon}}$.

If the limit of this quotient goes to $0$ as $n$ goes to $\infty$, then it must be the case that $\log_2(n)\in \mathcal{O}(n^{1-\epsilon})$ (can you prove this?).

And in fact this is what happens!

$$ \lim_{n\to \infty} \frac{\log_2(n)}{n^{1-\epsilon}} = \lim_{n\to \infty} \frac{\ln 2 \frac{1}{n}}{(1-\epsilon)n^{1-\epsilon -1}}=\lim_{n\to \infty} \frac{\ln(2)}{(1-\epsilon)}n^{\epsilon -1} = 0 $$

Where the first equality comes from L'Hôpital's rule and the limit goes to zero as $\epsilon < 1$.

Answer 2

Note: Here we analyse at some length OPs proof, identify some problems and propose an alternative while following OPs approach.

OPs proposed solution: $c=2^{\varepsilon}, n_0=4$

At first we check the proposed solution. OPs result $c=2^\varepsilon$ and $n_0=4$ gives \begin{align*} \log_2(n)\leq 2^{\varepsilon}n^{1-\varepsilon}\qquad\qquad n\geq 4 \end{align*}

We obtain by letting

• $n=4$: \begin{align*} &LHS:\qquad\log_2(4)=\log_2\left(2^2\right)=2\\ &RHS:\qquad2^{\varepsilon}\cdot 4^{1-\varepsilon}=2^{2-\varepsilon}>2\qquad\qquad 0\leq \varepsilon<1 \end{align*}

$n=4$ looks fine, but one more plausibility check with another power of $2$:

• $n=2^3$: \begin{align*} &LHS:\qquad\log_2(8)=\log_2\left(2^3\right)=3\\ &RHS:\qquad2^{\varepsilon}\cdot 8^{1-\varepsilon}=2^{3-2\varepsilon} \end{align*}

Since \begin{align*} 3\leq 2^{3-2\varepsilon} \,\,\Longleftrightarrow\,\, \log_2(3)\leq 3-2\varepsilon\\ \end{align*} we obtain \begin{align*} \varepsilon\leq \frac{3}{2}-\frac{1}{2}\log_2(3)\leq 0.7075\ldots \end{align*} We observe the last inequality is not valid for all $\varepsilon<1$ and this contradiction shows the proposed solution is not correct.

We will soon identify the problem, but first let's go on with OPs approach which is promising.

Taking logarithms:

It's a good idea to take logarithms in order to make the inequality better accessible. \begin{align*} \log_2(n)\leq c\cdot n^{1-\varepsilon}\tag{1} \end{align*}

Since the logarithm $\log_2$ is a strictly increasing function we obtain from (1) \begin{align*} \log_2\left(\log_2(n)\right)&\leq \log_2(c\cdot n^{1-\varepsilon})\\ &=\log_2(c)+(1-\varepsilon)\log_2(n)\tag{2} \end{align*}

$$ $$

OPs simplified inequality:

In order to estimate values for $c$ and $n_0$ OP tries to simplify the inequality and argues as follows:

(OP:) because $n$ is positive, $\log_2(n)$ will also be positive, so we have \begin{align*} \log_2\left(\log_2(n)\right)\leq(\log_{2}(c) + (1-\epsilon))\log_{2}(n) \end{align*}

• At first the minor deficiency: From $n$ being positive it does not follow that $\log_2(n)$ is positive, since with $n=1$ we have $\log_2(1)=0$. The next minor is that from being positive we cannot deduce the validity of the inequality. The value has to be $\geq 1$ to deduce the validity of the inequality.

• The major deficiency is that this is an estimation at the wrong side of the inequality, since we actually obtain the following inequality chain \begin{align*} \log_2\left(\log_2(n)\right)\leq\log_2(c)+(1-\varepsilon)\log_2(n)\leq(\log_{2}(c) + (1-\epsilon))\log_{2}(n) \end{align*}

Note, the inequality at the RHS is not helpful since determining $c$ and $n_0$ so that \begin{align*} \log_2\left(\log_2(n)\right)\leq(\log_{2}(c) + (1-\epsilon))\log_{2}(n) \qquad\qquad n\geq n_0 \end{align*} is valid does not imply that (2) is valid for $n\geq n_0$.

We need instead an expression $A(n,\varepsilon)$ which is in between: \begin{align*} \log_2\left(\log_2(n)\right)\leq A(n,\varepsilon)\leq\log_{2}(c) + (1-\epsilon)\log_{2}(n) \qquad\quad n\geq n_0 \end{align*}

If we can now find $c$ and $n_0$ with \begin{align*}\log_2\left(\log_2(n)\right)\leq A(n,\varepsilon)\qquad\qquad n\geq n_0\tag{3} \end{align*} then we may also deduce the validity of (2) from which the validity of (1) follows.

Note: It is this estimation at the wrong side which is the reason for the incorrect values of $c$ and $n_0$ stated by OP.

Another simplified inequality: $A(n,\varepsilon)$

We have to find $c$ and $n_0$ so that (2) is true for all $n\geq n_0$.

Since $\log_2\left(\log_2(n)\right)$ increases at a much slower rate than $\log_2(n)$ it is the factor $(1-\varepsilon)$ which can invalidate the inquality for small $n$. The factor is effective especially when $1-\varepsilon$ is very close to zero, which means $\varepsilon$ is very close to $1$.

So, we estimate $\varepsilon$ by a smaller value, which can be properly used for calculation.

Let $k=k(\varepsilon)\in\mathbb{N}$ with \begin{align*} 2^{-k}<1-\varepsilon \end{align*} then we are looking for $c$ and $n_0$ so that the following inequality chain is valid for $n\geq n_0$: \begin{align*} \log_2\left(\log_2(n)\right)\leq \log_2(c)+2^{-k}\log_2(n)\leq \log_2(c)+(1-\varepsilon)\log_2(n) \end{align*} We simplify the inequality chain even more by setting $c=1$. We obtain \begin{align*} \log_2\left(\log_2(n)\right)\leq 2^{-k}\log_2(n)\leq(1-\varepsilon)\log_2(n)\tag{4} \end{align*}

We obtain by setting $n=2{^{2^k}}$ in (4)

\begin{align*} k\leq 2^{-k}2^k=1 \end{align*}

This is not a satifying solution but it indicates a more promising approach. We obtain by setting $n=2{^{2^{2k}}}$ in (4)

\begin{align*} 2k\leq 2^{-k}2^{2k}=2^k \end{align*} which is true for all positive integers $k$,

resulting finally in the values \begin{align*} c=1\qquad\qquad\text{and}\qquad\qquad n_0=2{^{2^{2k}}} \end{align*} and we obtain according to (4) \begin{align*} \log_2(\log_2(n))&\leq 2^{-k}\log_2(n)\\ &\leq (1-\varepsilon)\log_2(n)\qquad\qquad n\geq n_0:=2^{2^{2k}} \end{align*}

$$ $$

Conclusion:

If we set $k=k(\varepsilon)\in\mathbb{N}$ so that $2^{-k}<1-\varepsilon$ and $c=1$ then \begin{align*} \log_2(n)\leq n^{1-\varepsilon}\qquad\qquad n\geq n_0:=2^{2^{2k}} \end{align*}