1
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ Try using the limit definition of big-O instead, and applying Lhopital's rule $\endgroup$
    – nir shahar
    Apr 30, 2021 at 9:36
  • $\begingroup$ @nirshahar we are not allowed to use the limit definition in our course $\endgroup$ Apr 30, 2021 at 9:37
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Steven
    Apr 30, 2021 at 9:38
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Steven
    Apr 30, 2021 at 9:43
  • 2
    $\begingroup$ 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. $\endgroup$
    – zkutch
    Apr 30, 2021 at 15:25

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.