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!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
lim_n->infinity: (n!*n^k) / n! = lim_n->infinity n^k = infinity
n!*n^k is NOT in
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
g(n) differs "only"
k is constant and does not change (for example
g(n) is always ~100times higher, no matter if
n=1000000), then these functions have same complexity.
g(n) is 100times higher for
n=10000 and 80times higher for
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!*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.