Big-O Square Root Magazine

Question

Generally speaking, is it always always true?

log (n) = O (n ^{a / (a ​​+ 1)} )? ST a is any constant positive integer, possibly very large.

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

Answer 1

As a function of go, log (n) always grows slower than n of ^{any cardinality} when n becomes large. See https://math.stackexchange.com/questions/1663818/does-the-logarithm-function-grow-slower-than-any-polynomial for confirmation.

So, while a is a constant positive integer, it doesn't really matter what its value is, since you can always find the 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 this intuitively: n ^{a / (a ​​+ 1)} approaches n when a becomes large. Naturally, log (n) is always O (n).

Answer 2

The basic fact is that because of the concavity of the logarithm, it is always lower than its tangent. So

log(x) <= log(e) + 1/e * (xe) = x/e 

In this way,

 log(n) = O(n). 

Now you need to apply the laws of the logarithm to find

 log(n) = 1/c * log(n^c) <= 1/(ce) * n^c 

and therefore log(n)=O(n^c) for any positive C

Answer 3

If you mean log(n)∈O(n^(a/(a+1)) , yes, this is true for all positive integers for a, because a/a+1 < 1 => n^(a/(a+1) ∈ O(n) and due to log(n) ∈ O(n) => log(n) ∈ O(n^(a/(a+1))