Докажите или опровергните следующее предположение (Big O Notation)

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отношение обратное.