algorithm - 证明或反驳以下含义（大 O 表示法）

Question

我无法证明这一点：

f(n) = O(g(n))暗示f(n)^k = O(g(n)^k)

where k is element of the natural, positiv numbers

我在网上找到了类似的例子。但我不确定为这个例子实施这些解决方案是否正确。

Answer 1

回到big-o 的定义。

f(n) = O(g(n)) <=> \exists M \in R+,
                   \exists n_0 \in N,
                   such that:
                   \forall n > n_0
                   |f(n)| < M.|g(n)|

很明显，如果k > 0那么|f(n)|^k < (M.|g(n)|)^k。

如果k < 0，则关系是相反的。