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?
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?
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.
Possible duplicate of How to prove the asymptotic order of an algorithm?
– Victor Stafusa
See in this question that I Linkei as duplicate, all the answers from there address this.
– Victor Stafusa
Related: https://answall.com/q/268409/64969
– Jefferson Quesado
I’ve read all these publications, but I still don’t understand --'
– thaismota17
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.
– Jefferson Quesado