# big o - 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?

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!)`

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.