Help with little-oh given $f(n) = n^\epsilon$ and $g(n) = (\lg n)^4$

Question

Problem

Given $f(n) = n^\epsilon, \epsilon > 0$ and $g(n) = (\lg n)^4$ find a little-oh relation between $f(n)$ and $g(n)$.

Are $f(n)$ and $g(n)$ asymptotically different? Are they polynomially different?

Note that $\lg n \equiv \log_2n$.

---

Solution Attempt

I've started by using the formal definition of little-oh to set up the problem in both directions. I'm not sure which direction holds because $\epsilon$ can take on a range of values. $$ n^\epsilon \in o((\lg n)^4) \iff \forall c > 0, \exists n_0 > 0 \enspace \text{s.t.} \enspace n^\epsilon < c(\lg n)^4, \enspace \forall n_0 \ge 0$$ $$ (\lg n)^4 \in o(n^\epsilon) \iff\forall c > 0, \exists n_0 > 0 \enspace \text{s.t.} \enspace (\lg n)^4 < cn^\epsilon, \enspace \forall n_0 \ge 0$$

From properties of logarithms, I know I can write $n^\epsilon$ as $2^{\epsilon\cdot\lg n}$, but I'm not sure if this helps me get anywhere.

I also know that $f(n) \in o(g(n))$ implies $$ \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0 $$ since little-oh intuitively means that $f(n)$ grows asymptotically slower than $g(n)$. So if I can prove either $$\lim_{n\to\infty} \frac{n^\epsilon}{(\lg n)^4} = 0 \quad \text{or} \quad \lim_{n\to\infty} \frac{(\lg n)^4}{n^\epsilon} = 0 $$ then I can show a little-oh relation. However, I'm not sure how to evaluate these limits, since L'Hopital's rule just yields increasingly complicated derivatives for $(\lg n)^4$.

Can someone guide me toward a solution?

Answer 1

Take the fourth root of your second ratio, and then you will have $\log n$ in the numerator and $n^\delta$ in the denominator where $\delta = \epsilon / 4 > 0$. Then apply L'Hopitals. If the fourth root of the ratio goes to zero, then so does the original ratio

Answer 2

By changing $\epsilon$ by $\epsilon/4$ you have just to prove that: $$\lim_{n\to\infty} \frac{\text{log}n}{n^\epsilon} = 0$$ But if we multiply by $\epsilon$ (which does not change the result) and by substitution $m= n^{\epsilon}$ we get : $$\epsilon \lim_{n\to\infty} \frac{\text{log}n}{n^\epsilon} =\lim_{n\to\infty} \frac{\epsilon\text{log}n}{n^\epsilon}=\lim_{n\to\infty} \frac{\text{log}n^\epsilon}{n^\epsilon}= \lim_{m\to\infty} \frac{\text{log}m}{m}$$

so you need only to prove that: $$\lim_{n\to\infty} \frac{\text{log}n}{n}=0$$

which is well known

Answer 3

One solution—not the easiest to find, but a more general one that could be helpful in the future—is to show:

If $g(n)$ and $f(n)$ both tend to infinity, and $\log g(n) = o(\log f(n))$, then $g(n) = o(f(n))$.

Once proved, this changes your problem into showing that $4\log\log n = o(\epsilon \log n)$, which leads to much more straightforward calculus (and also shows, along the way, that the constants $\epsilon$ and $4$ aren't that relevant).

(It's also a good exercise to convince yourself that the following statement is false: If $g(n)$ and $f(n)$ both tend to infinity, and $\log g(n) = O(\log f(n))$, then $g(n) = O(f(n))$.)