Big-O of log versus square root

Question

Generally speaking, is the following always true?

log(n) = O(n^a/(a+1))? s.t. a is any constant positive integer, perhaps very large.

If not, what is the largest value of a for which this statement will hold true?

Answer 1

As functions go, log(n) always grows slower than n^{any power} when n gets large. See https://math.stackexchange.com/questions/1663818/does-the-logarithm-function-grow-slower-than-any-polynomial for proof.

So as long as a is a constant positive integer, it really doesn't matter what its value is, as it will always be possible to find constants C and k such that log(n) <= |C(n^a/(a+1)| + k, which is the definition of big-O.

However, you can also understand it intuitively: n^a/(a+1) approaches n as a becomes large. Naturally, log(n) is always O(n).