Asymptotic complexity of logarithmic functions

问题:

I know that in terms of complexity, O(logn) is faster than O(n), which is faster than O(nlogn), which is faster than O(n2). But what about O(n2) and O(n2log), or O(n2.001) and O(n2log):

T1(n)=n^2 + n^2logn

What is the big Oh and omega of this function? Also, what's little oh? versus:

T2(n)=n^2.001 + n^2logn

Is there any difference in big Oh now? I'm having trouble understanding how to compare logn with powers of n. As in, is logn approximately n^0.000000...1 or n^1.000000...1?

回答1:

O(n^k) is faster than O(n^k') for all k, k' >= 0 and k' > k

O(n^2) would be faster than O(n^2*logn)

Note that you can only ignore constants, nothing involving the input size can be ignored.

Thus, complexity of T(n)=n^2 + n^2logn would be the worse of the two, which is O(n^2logn).

---

Little-oh

Little oh in loose terms is a guaranteed upper bound. Yes, it is called little, and it is more restrictive.

n^2 = O(n^k) for k >= 2 but n^2 = o(n^k) for k > 2

Practically, it is Big-Oh which takes most of the limelight.

---

What about T(n)= n^2.001 + n^2logn?

We have n^2.001 = n²*n^0.001 and n² * log(n).

To settle the question, we need to figure out what would eventually be bigger, n^0.001 or log(n).

It turns out that a function of the form n^k with k > 0 will eventually take over log(n) for a sufficiently large n.

Same is the case here, and thus T(n) = O(n^2.001).

Practically though, log(n) will be larger than n^0.001.

(10³³⁰⁰)^0.001 < log(10³³⁰⁰) (1995.6 < 3300), and the sufficiently large n in this case would be just around 10³⁶⁵⁰, an astronomical number.

Worth mentioning again, 10³⁶⁵⁰. There are 10⁸² atoms in the universe.

回答2:

T(n)=n^2 + n^2logn

What is the big Oh and omega of this function? Also, what's little oh?

Quoting a previous answer:

Don't forget big O notation represents a set. O(g(n)) is the set of of all function f such that f does not grows faster than g, formally is the same is saying that there exists C and n0 such that we have |f(n)| <= C|g(n)| for every n >= n0. The expression f(n) = O(g(n)) is a shorthand for saying that f(n) is in the set O(g(n))

Also you can think of big O as ≤ and of small o as < (reference). So you care of more of finding relevant big O bound than small o. In your case it's even appropriate to use big theta which is =. Since n^2 log n dominates n^2 it's true that

T1(n)=n^2 + n^2logn = Ө(n^2 logn)

Now the second part. log n grows so slowly that even n^e, e > 0 dominates it. Interestingly, you can even prove that lim n^e/(logn)^k=inf as n goes to infinity. From this you have that n^0.001 dominates log n then

T2(n)=n^2.001 + n^2logn = Ө(n^2.001).

If f(n) = Ө(g(n)) it's also true that f(n) = O(g(n)) so to answer your question:

• T1(n)=O(n^2 logn)
• T2(n)=O(n^2.001)