I couldn't prove this:
f(n) = O(g(n))
implies f(n)^k = O(g(n)^k)
where k is element of the natural, positiv numbers
I've found similar examples on the internet. But I'm not sure if it's right to implement those solutions for this example.
Go back to the 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)|
It is obvious that if k > 0
then |f(n)|^k < (M.|g(n)|)^k
.
If k < 0
, the relation is inversed.