<s>[INST] Prove that $\log_{2}(n) = O(n^{1-\epsilon})$ for any $0 \leq \epsilon < 1$ 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$.
 [/INST] 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*}

</s>