CODEWITHSUNDEEP
algorithmbig-oimplication
Elfie
Elfie

Reputation: 369

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.

Upvotes: 1

Views: 1313

Answers (1)

fjardon
fjardon

Reputation: 7996

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.

Upvotes: 1

Related Questions