Seja T uma função que satisfaz a recorrência T(n) = 2 T(⌊n/2⌋) + 7n + 2. Considere o seguinte
Problema: provar, por indução em n, que T(n) = Ο(n lg n).
Ao se deparar com um problema desse tipo (quaisquer que sejam os detalhes da recorrência e da expressão Ο( … )), muitos computólogos inexperientes tentam provar a afirmação T(n) = Ο(n lg n) diretamente, usando a proposição T(n/2) = Ο((n/2) lg (n/2)) como hipótese de indução. Isto não faz o menor sentido!
Para resolver o problema, é preciso antes especificar explicitamente os valores dos parâmetros c e n0 que aparecem na definição da notação Ο( ). No nosso exemplo concreto, o que devemos mostrar é que
| T(n) ≤ 10 n lg n para todo n ≥ 2. | (*) |
Agora sim, a afirmação (*) tem chance de ser provada (tomando a desigualdade T(n/2) ≤ 10 (n/2) lg (n/2) como hipótese de indução).
A solução final do problema é um mero corolário de (*).