algorithm - 证明或反驳以下推论(大 O 表示法)

Question

我无法证明这一点:

f(n) = O(g(n)) 意味着 f(n)^​​k = O(g(n)^k)

其中 k 是自然正数的元素

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

Answer 1

返回definition of 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 , 关系相反。