次の含意（ランダウの記号）

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の場合、その関係は逆になります。