The questionI'm solving exercise 3-2 from the book Introduction to algorithm (Cormen Leiserson, 3rd edition).I'm able to prove that $(log(n))^k \in O(n^\epsilon)$ (see below) but I'm not able to prove that $(log(n))^k \in o(n^\epsilon)$. Do you have any idea about how to complete the exercise?Big-O part solution$(log(n))^k \in O(n^\epsilon)$ if and only if exists constant $c>0$ and $n_0$ such that $log(n)^k \leq c*n^\epsilon$ for all $n>n_0$.We can re-write the terms in this way:$log(n)^k=e^{log(log(n)^k}=e^{k*log(log(n))}$$n^\epsilon=e^{log(n)^\epsilon}=e^{\epsilon*log(n)}$$\frac{log(n)^k}{n^\epsilon}=\frac{e^{k*log(log(n))}}{e^{\epsilon*log(n)}}$ will imply $\frac{k*log(log(n))}{\epsilon*log(n)}=\frac{k}{\epsilon} * \frac{log(log(n))}{log(n)}$. Note that $0 \le \frac{log(log(n))}{log(n)} \le 1$ forall $n>e$, and also $\lim\limits_{n \to \infty} \frac{log(log(n))}{log(n)}=0$Then:$log(n)^k \leq c*n^\epsilon$$\frac{log(n)^k}{n^\epsilon} \le c$ with $n \not= 0$$c \ge \frac{k}{\epsilon} * \frac{log(log(n))}{log(n)}$true for $c=\frac{k}{\epsilon}$ and $n_0 = 3$ (any value above $e$)Little-O part solutionLittle-o definition says that $log(n)^k \leq c*n^\epsilon$ for all constant $c>0$. I'm sure that it's true for any constant $c \ge \frac{k}{\epsilon}$ (see above). For each constant between $0$ and $\frac{k}{\epsilon}$ I think I should find a value of $n_0$ that makes the inequality true (that certainly exists because $\lim\limits_{n \to \infty} \frac{log(log(n))}{log(n)}=0$).How can I express the answer?
Relative asymthotic growth of two functions
asymptotics