证明或反驳以下含义（大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

回到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，则关系反转。