Asymptotic complexity of logarithms and degrees

Question

So obviously log (n) is O (n). But what about (log (n)) ^ 2? What about sqrt (n) or log (n) - what are the limitations of what?

There is a family of comparisons:
n ^ a vs (log (n)) ^ b

I often come across these comparisons, and I have never had a good way to solve them. Tips for tactics solving the general case?

Thanks,
Ian

EDIT: I'm not talking about the computational complexity of computing the values ​​of these functions. I am talking about the functions themselves. For example, f (n) = n is the upper bound on g (n) = log (n), since f (n) <= c * g (n) for c = 1 and n0> 0.

Answer 1

log (n) ^ a is always O (n ^ b), for any positive constants a, b.

Are you looking for evidence? All such problems can be reduced to the fact that log (n) - O (n), with the following trick:

log (n) ^ a = O (n ^ b) is equivalent to: log (n) = O (n ^ {b / a}), since increasing to the power of 1 / a is an increasing function. This is equivalent to log (m ^ {a / b}) = O (m), setting m = n ^ {b / a}. This is equivalent to log (m) = O (m), since log (m ^ {a / b}) = (a / b) * log (m).

You can prove that log (n) = O (n) by induction by focusing on the case where n is a power of 2.

Answer 2

I often come across these comparisons (...) Tips for tactics solving the general case?

How are you, how about the general case , and that you are much versed in such matters. Here is what I recommend:

Use the BigO notation definition constraint as soon as you know:

f(n) = O(g(n)) iff limit (n approaches +inf) f(n)/g(n) exists and is not +inf 

You can use a Computer Algebra system , for example open source Maxima , here is the Maxima Documentation on Limits .

For more details and an example, check out this answer.

Answer 3

 log n -- O(log n) sqrt n -- O(sqrt n) n^2 -- O(n^2) (log n)^2 -- O((log n)^2) 

n^a compared to (log(n))^b

You need either the bases or the same powers. So use your math to change n^a to log(n)^(whatever it gets to get this base) or (whatever it gets to get this power)^b . No general case