Algorithm complexity - Big O notation

Asked

Viewed 576 times

3

The function f(n) = n3 + 2 asymptotically dominates the function g(n) = 200n2 + 5, for a value of n large enough. That is to say, g(n) is O(f(n))

How can I prove that statement is true?

  • 1

    Possible duplicate of How to prove the asymptotic order of an algorithm?

  • 1

    See in this question that I Linkei as duplicate, all the answers from there address this.

  • Related: https://answall.com/q/268409/64969

  • I’ve read all these publications, but I still don’t understand --'

  • Take a very affectionate look at Isac’s response. Try to do the calculations along with it. I particularly think his answer is the best of 3 to try to understand how to prove the asymptotic order of functions.

1 answer

3

Prove that g(n) is O(f(n)) is the same as saying that there are constants c and n0 (both positive) such that

0 ≤ g(n) ≤ cf(n), para todo n ≥ n0

I mean, we have to prove that 

0 ≤ 200n2 + 5 ≤ c(n3 + 2), para todo n ≥ n0
0 ≤ 200n2 + 5 ≤ cn3 + 2c, para todo n ≥ n0

Note that 0 ≤ 200n2 + 5 is redundant as 200n2 + 5 is always positive. Therefore, it is sufficient to analyze only

200n2 + 5 ≤ cn3 + 2c, para todo n ≥ n0

The point now is to find the stories c and n0 which satisfy the above condition. Keep in mind that any pair of values c and n0 satisfying the condition is valid.

If we choose c = 100 and n0 = 1, the condition will be valid:

200n2 + 5 ≤ 100n3 + 200, para todo n ≥ 1

Another choice would be c = 69 and n0 = 1

200n2 + 5 ≤ 69n3 + 138, para todo n ≥ 1

Therefore, as there are a couple of counters c and n0 satisfying 0 ≤ g(n) ≤ cf(n), for all n ≥ n0, then g(n) is O(f(n)).

References

CORMEN, T. H. et al. Algorithms: theory and practice. 3 ed. Rio de Janeiro: Elsevier, 2012.

Browser other questions tagged

You are not signed in. Login or sign up in order to post.