# Show that $(\log(n))^\alpha = O(n^\beta)$

I am trying to show that $$\forall \beta \gt0, \log(n^\alpha) = O(n^\beta)$$, however I cannot use the limit definition, as demonstrated in similar questions on the forum.

First I show that $$\log(n^\alpha) = O(n)$$, using the following method:

$$\log(n^\alpha) = \alpha \cdot \log(n) \leq \alpha \cdot n$$ Thus for $$c=\alpha^\alpha, n_0=0$$, we have $$(\log(n))^\alpha \leq c \cdot n$$ which implies $$\log(n^\alpha) = O(n)$$

Now I will show $$\forall \beta \gt0, \log(n^\alpha) = O(n^\beta)$$, we have two cases

$$\beta \ge 1$$: Since $$\forall n \ge1, n\leq n^\beta$$, then from the above result, for $$c=\alpha^\alpha, n_0 = 1$$, we have $$\log(n^\alpha) \le c \cdot n^\beta$$ which implies $$\log(n^\alpha) = O(n^\beta)$$

$$0 \lt \beta \lt 1$$: I can't seem to find a series of inequalities, as shown above, that prove $$\log(n^\alpha) =O(n^\beta)$$ in this case

• Try using the limit definition of big-O instead, and applying Lhopital's rule Apr 30, 2021 at 9:36
• @nirshahar we are not allowed to use the limit definition in our course Apr 30, 2021 at 9:37
• Why are you not allowed to use limits? If $f(n)=O(g(n))$ in limit definition then $f(n)=O(g(n))$ also in the definition with $n_0$ and $c$. Apr 30, 2021 at 9:38
• You can always establish that $\lim_{n \to \infty} \frac{(\log n)^\alpha}{n^\beta} = 0$ and then formally show that this implies the existence of a $n_0$ and of a $c>0$ such that $(\log n)^\alpha < c n^\beta$ for any $n \ge n_0$. Apr 30, 2021 at 9:43
• I think you mean $\beta \gt 0$ @Steven (mentioned and proved here cs.stackexchange.com/questions/139476/…). One more: I have doubt, that someone who reject Lhopital, accept derivative. Apr 30, 2021 at 15:25

You can use the following identities: $$(\ln n)^a \le n^\beta \iff \ln (\ln n)^a \le \ln n^\beta \iff a \ln \ln n \le \beta \ln n.$$
This is trivial if $$\alpha \le 0$$, so we consider the case $$\alpha > 0$$.
For simplicity substitute $$t= \ln \ln n$$ and $$\gamma = \frac{\alpha}{\beta}$$. Notice that $$\gamma \ge 0$$. We obtain: $$\gamma t \le e^t \iff \gamma t - e^t \le 0$$
To show that $$\alpha t \le \beta e^t$$ for sufficiently large $$t$$, we take the derivative of $$h(t) = \gamma t - e^t$$: $$h'(t) =\gamma - e^t.$$
This shows that for $$t \ge \ln \gamma$$, $$h(t)$$ is monotonically non-increasing. Moreover, for $$t=\ln \gamma$$ we already have $$h(t) \le 0$$, indeed $$h(\ln \gamma) =\ln \gamma-\gamma \le 0$$ since the logarithm is a monotonically increasing function.
Hence, in the definition of big-Oh with $$n_0$$ and $$c$$, we can pick $$n_0 = \ln \gamma = \ln \frac{\alpha}{\beta}$$ and $$c=1$$.