问题描述:

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

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.

您可能感兴趣的文章：

- Can't locate bits/wordsize.ph perl PAR-Packer error
- java - String-array puts a comma after item text
- ios - How to generate a Random Floating point Number in range, Swift
- d3.js - How to include d3 on JavaScript non html file?
- javascript - js: getting substring starting by char
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**