algorithmbig-oimplication

Prove or disprove the following implication (Big O Notation)


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.


Solution

  • 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.