0

I'm a CS freshman. In my discrete math textbook, it says

... whenever b > 1 and c and d are positive, we have

$(\log_bn)^c$ is $O(n^d)$, but $n^d$ is not $O((\log_bn)^c)$

But why? Using Wolframalpha I see the plot show for b=2,c=3,d=1, it the logarithm still grows slower than the polynomial, but I don't know how to understand this mathematically. Is there a way to prove that for any arbitrary c and b, while d=1, $(\log_bn)^c$ is $O(n^d)$?

RexYuan
  • 140

1 Answers1

1

Consider the limit

$$\lim _ {x\rightarrow\infty}\frac{\log^m x}{x^n}$$

where $m>0$ and $n>0$. That limit will be 0 (just use lhopital), meaning any positive power of $\log x$ is insignificant compared to any positive power of $x$ as $x\rightarrow\infty$

Gappy Hilmore
  • 3,937
  • That's a interesting solution! My course didn't use any limits on the topic of asymptotic notations – RexYuan Jun 10 '15 at 07:41