1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Oct 22 '19 at 9:09
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

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