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.
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$– gnasher729Oct 22, 2019 at 9:09
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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)).$
$\begingroup$
$\endgroup$
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$
