I'm working on a problem where I am given f(n) = n^2 * (log(n))^-1, and g(n) = n(log(n))^2, and asked to determine whether f=O(g), f=omega(g), or both (f=theta(g)).
This problem can be generalized to (n^a)*log(n)^b and (n^c)*log(n)^d
I understand that any polynomial dominates any logarithm, for example n dominates log(n) and furthermore n^2 dominates nlog(n) however I am unsure about how to adapt this to more complicated problems, for example:
or better yet:
Does the polynomial term always determine if f dominates g, or vise versa? If so, why? and if not, how can the problem be solved?
Thanks!
Answer: n^a * log(n)^b dominates n^c * log(n)^d if a > c. In other words, you only need to look at the polynomial part. (Unless of course a=c, in which case you look at the polylog part.)
This is because polylogarithmic functions are always asymptotically less than polynomial functions. More precisely, if p(n) = a*(log n)^b (p is polylogarithmic in n), then p(n) = o(n^epsilon) for any epsilon > 0 (see this Wikipedia page for the formal statement, and this answer for a proof).
So, we have n^a * log(n)^b = o(n^(a + epsilon)) for any epsilon > 0. From this it should be easy to arrive at the answer above.