A função f(n) = n3 + 2
domina assintoticamente a função g(n) = 200n2 + 5
,
para um valor de n suficientemente grande.
Ou seja, g(n)
é O(f(n))
Como posso provar que essa afirmação é verdadeira?
Stack Overflow em Português é um site de perguntas e respostas para programadores profissionais e entusiastas. Leva apenas um minuto para se inscrever.
Inscreva-se para participar desta comunidadeA função f(n) = n3 + 2
domina assintoticamente a função g(n) = 200n2 + 5
,
para um valor de n suficientemente grande.
Ou seja, g(n)
é O(f(n))
Como posso provar que essa afirmação é verdadeira?
Provar que g(n)
é O(f(n))
é o mesmo que dizer que existem constantes c
e n0
(ambas positivas) tais que
0 ≤ g(n) ≤ cf(n), para todo n ≥ n0
Ou seja, temos que provar que
0 ≤ 200n2 + 5 ≤ c(n3 + 2), para todo n ≥ n0 0 ≤ 200n2 + 5 ≤ cn3 + 2c, para todo n ≥ n0
Observe que 0 ≤ 200n2 + 5
é redundante, pois 200n2 + 5
é sempre positivo. Logo, é suficiente analisar apenas
200n2 + 5 ≤ cn3 + 2c, para todo n ≥ n0
O ponto agora é encontrar as contantes c
e n0
que satisfaçam a condição anterior. Tenha em mente que qualquer par de valores c
e n0
que satisfaça a condição é válido.
Se escolhermos c = 100
e n0 = 1
, a condição será válida:
200n2 + 5 ≤ 100n3 + 200, para todo n ≥ 1
Outra escolha seria c = 69
e n0 = 1
200n2 + 5 ≤ 69n3 + 138, para todo n ≥ 1
Portanto, como existe um par de contantes c
e n0
que satisfaz 0 ≤ g(n) ≤ cf(n)
, para todo n ≥ n0
, então g(n)
é O(f(n))
.
Referências
CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.