The f(n) = n3 + 2 function asymptotically dominates the g(n) = 200n2 + 5 function,
for a sufficiently large n value.
That is, g(n) is O(f(n))
How can I prove that this statement is true?
Complexity of algorithms - Big O notation
1
asked by anonymous 03.04.2018 / 16:51
1 answer
0
Proof 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
That is, 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, since 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 c and n0 counters that satisfy the previous condition. Keep in mind that any pair of values c and n0 that satisfies 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, since there is a pair of c and n0 counters that satisfy 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.
02.09.2018 / 17:14