# Question about growth rates of functions involving n and logn

I was studying for an algorithm exam and was having trouble answering (or rather proving) one of the practice problems. I want to find the correct symbol among $$o$$, $$\omega$$, $$\Theta$$ that would best describe the relationship between two functions $$f(n) = (\log n)^{100} + n^{0.01}$$ and $$g(n) = (\log n)^{50} + n^{0.05}$$. Intuitively, it seems like $$f(n) \in o(g(n))$$ because the extra $$n^{0.04}$$ in $$g(n)$$ grows much faster than the $$\log^{50} n$$ in $$f(n)$$. However, I am not really sure how to prove this using first principles. Could anyone provide any suggestions? Thanks in advance.

• It may be easier if you let n = 2^k. K^100 + 2^0.01k vs k^50 + 2^0.05k. Find where the latter becomes larger, and where increasing k by 20 doesn’t double the first one. – gnasher729 Oct 22 '19 at 9:09

There exists some $$n_0 > 0$$ such that $$\log n \le n^{0.0001}$$ for all $$n \ge n_0$$. This can be seen, e.g., by taking the limit: $$\lim_{n \to \infty} \frac{\log n}{n^{0.0001}} = \lim_{n \to \infty} \frac{10000}{ n^{0.0001}} = 0.$$

This means that, for $$n \ge n_0$$, $$f(n) = \log^{100} n + n^{0.01} \le \left( n^{0.0001} \right)^{100} + n^{0.01} = 2n^{0.01}.$$

Therefore, using the fact that $$g(n) \ge n^{0.05}$$: $$\lim_{n \to \infty} \frac{f(n)}{g(n)} \le \lim_{n \to \infty} \frac{2n^{0.01}}{n^{0.05}} = \lim_{n \to \infty} \frac{2}{n^{0.04}} = 0,$$ implying that $$f(n)=o(g(n)).$$

Ok this is not a good way to do it but here is my approach.

So, here it suffices to prove $$\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$$. That will imply $$f(n) = o(g(n))$$

proof of $$\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$$

$$\lim_{n\to\infty} \frac{f(n)}{g(n)}$$

$$= \lim_{n\to\infty} \frac{(log(n))^{100} + n^{0.01}}{(log(n))^{50} + n^{0.05}}$$

$$= \lim_{n\to\infty} \frac{100.(log(n))^{99}. \frac{1}{n} + 0.01(n^{-0.99})}{50.(log(n))^{49}. \frac{1}{n} + 0.05(n^{-0.95})}$$ $$\because\text{(L'hopital's rule)}$$

Now, multiply lower and upper term by $$n$$

$$= \lim_{n\to\infty} \frac{100.(log(n))^{99} + 0.01(n^{0.01})}{50.(log(n))^{49} + 0.05(n^{0.05})}$$ ....

....

....

. repeating above two steps 100 times we'll get

$$= \lim_{n\to\infty} \frac{100! + 0.01^{100}(n^{0.01})}{0.05^{100}(n^{0.05})}$$

$$=0$$