CODEWITHSUNDEEP
algorithmmathtime-complexitybig-ologarithm
CaptainForge
CaptainForge

Reputation: 1385

Big-O of log versus square root

Generally speaking, is the following always true?

log(n) = O(na/(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?

Upvotes: 11

Views: 13453

Answers (3)

pymaxion
pymaxion

Reputation: 403

As functions go, log(n) always grows slower than nany 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(na/(a+1)| + k, which is the definition of big-O.

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

Upvotes: 10

Lutz Lehmann
Lutz Lehmann

Reputation: 25992

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

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

Thus

log(n) = O(n).

Now it is only necessary to apply logarithm laws to find

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

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

Upvotes: 3

Exagon
Exagon

Reputation: 5088

If you mean log(n)∈O(n^(a/(a+1)), yes this is true for all positiv Integers for a, because a/a+1 < 1 => n^(a/(a+1) ∈ O(n) and because of log(n) ∈ O(n) => log(n) ∈ O(n^(a/(a+1))

Upvotes: 0

Related Questions