0
$\begingroup$

Let $a,b>0$. Prove $\left(\log\left(n\right)\right)^{a}=O\left(n^{b}\right)$.

I'm supposed to find an algorithm to find the log(n) largest elements in an array and return them sorted and explain why it's bounded by $O(n^{b})$, but the thing is I'm having trouble proving the above and I'm kind of stuck.. Any tips?

$\endgroup$
1
$\begingroup$

As $a$ is fixed, then you can omit it from requirements because for $a \gt 0$ inequality $(\log n)^a \leqslant C n^b$ is equivalent $\log n \leqslant C^{\frac{1}{a}}n^{\frac{b}{a}}$. Denoting $0 \lt \frac{b}{a}=\alpha $ we obtain, that it's enough to proof $\log n \in O(n^\alpha)$ for $\alpha \gt 0$.

To simplify, we can consider $\log n$ with base $e$, because the difference with the other base will be constant factor.

So, last step will be $$\lim\limits_{n \to \infty}\frac{\ln n}{n^\alpha} = \lim\limits_{n \to \infty}\frac{1}{\alpha n^\alpha}=0$$

We see, that a more strong result with $o$-little is fair: $\forall \alpha \gt 0$ we have $\log n \in o(n^\alpha) \subset O(n^\alpha)$.

$\endgroup$
0
$\begingroup$

Try using the limit definitions for big-O, and try using Lhopital's rule

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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