Problema 7.2-1 do Cormen

[Ricardo Correa]

Oi Pessoal,

Alguem conseguiu resolver o problema 7.2-1 do Cormen ?

Eu cheguei em um ponto que não sei justificar muito bem o final.

Problema: Use the substitution method to prove that the recurrence T(n) = T(n - 1) + theta(n) has the solution T(n) = theta(n²), as claimed at the beginning of Section 7.2.

Consegui desenvolver assim:
HI: T(n) = theta(n²)

 T(n) = T(n-1) + dn
 T(n) <= c(n-1)² + dn  (aplicando a HI)
 T(n) <= cn² - 2cn - c + dn
 T(n) <= cn² + n(d - 2c) - c

Isso é valido para n(d - 2c) - c >= 0, mas isso não parece bom para resolver este problema
Alguem chegou a uma melhor solução ?

Obrigado,
Ricardo

[Carla Négri]

Olá,
Estou enviando minha resposta em anexo.
Acho que na sua falta isolar o c, que é o procurado.
Além disso, pra provar theta vc tem que provar tanto omega quanto big-O.

--
Carla Négri Lintzmayer (@carlanegri)
Mestranda em Ciência da Computação pela Universidade Estadual de Campinas
Bacharel em Ciência da Computação pela Universidade Estadual de Maringá

"Política é para o presente, mas uma equação é para a eternidade." (Albert Einstein)

[Ricardo Correa]

Valeu Carla! agora entendi :)

2012/5/12 Carla Négri <carla...@gmail.com>

[Sigrid Ortiz]

Disculpa voce nao tem o analisis da perguntinha problema 2-1 do cormen pelo amor de Deus me ayude

[L.]

7.2-1

--
Você recebeu essa mensagem porque está inscrito no grupo "Algorítmos-1s-2012" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para algoritmos-1s-2...@googlegroups.com.
Para mais opções, acesse https://groups.google.com/d/optout.

--

"No debe haber barreras para la libertad de preguntar. No hay sitio
para el dogma en la ciencia. El cienti­fico es libre y debe ser libre
para hacer cualquier pregunta, para dudar de cualquier aseveracion,
para buscar cualquier evidencia, para corregir cualquier error"
(Oppenheimer)