Which Big-O grows faster asymptotically

问题:

I have gotten into an argument/debate recently and I am trying to get a clear verdict of the correct solution.

It is well known that n! grows very quickly, but exactly how quickly, enough to "hide" all additional constants that might be added to it?

Let's assume I have this silly & simple program (no particular language):

for i from 0 to n! do:
    ; // nothing

Given that the input is n, then the complexity of this is obviously O(n!) (or even ϴ(n!) but this isn't relevant here).

Now let's assume this program:

for i from 0 to n do:
    for j from 0 to n do:
        for k from 0 to n! do:
            ; // nothing

Bob claims: "This program's complexity is obviously O(n)O(n)O(n!) = O(n!n^2) = O((n+2)!)."

Alice responds: "I agree with you bob, but actually it would be sufficient if you said that the complexity is O(n!) since O(n!n^k) = O(n!) for any k >= 1 constant."

Is Alice right in her note of Bob's analysis?

回答1:

Alice is wrong, and Bob is right.

Recall an equivalent definition to big O notation when using limit:

f(n) is in O(g(n)) iff 
lim_n->infinity: f(n)/g(n) < infinity

For any k>0:

lim_n->infinity: (n!*n^k) / n! = lim_n->infinity n^k = infinity

And thus, n!*n^k is NOT in O(n!)

回答2:

Amit solution is perfect, I would only add more "human" solution, because understanding definition can be difficult for beginners.

The definition basically says - if you are increasing the value n and the methods f(n) and g(n) differs "only" k-times, where k is constant and does not change (for example g(n) is always ~100times higher, no matter if n=10000 or n=1000000), then these functions have same complexity.

If the g(n) is 100times higher for n=10000 and 80times higher for n=1000000, then f(n) has higher complexity! Because as the n grows and grows, the f(n) would eventually at some point reach the g(n) and then it will grow more and more compare to g(n). In complexity theories, you are interested in, how it will end in "infinity" (or more imaginable extremely HIGH values of n).

if you compare n! and n!*n^2, you can see, that for n=10, the second function has 10^2=100 times higher value. For n=1000, it has 1000^2=1000000 times higher value. And as you can imagine, the difference will grow.