哪个Big-O渐进式增长得更快

Question

我最近已经进入争论/辩论,我试图得到正确解决方案的明确判决.

众所周知,n!增长非常快,但究竟有多快,足以"隐藏"可能添加到其中的所有其他常量？

让我们假设我有这个愚蠢而简单的程序(没有特定的语言):

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

鉴于输入是n,那么这的复杂性显然O(n!)(或者甚至?(n!)是这里不相关).

现在让我们假设这个程序:

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

鲍勃声称:"这个程序的复杂性显而易见O(n)O(n)O(n!) = O(n!n^2) = O((n+2)!)."

爱丽丝回应说:"我同意你的鲍勃,但实际上这将是足够的,如果你说的复杂性O(n!),因为O(n!n^k) = O(n!)对于任何k >= 1常量".

爱丽丝是否正确地记录了鲍勃的分析？

Answer 1

爱丽丝错了,鲍勃是对的.

使用限制时,回想一下大O符号的等效定义:

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

任何k>0:

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

因此,n!*n^k不在O(n!)