algorithm - 次の含意を証明または反証してください (Big 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、関係が逆になります。