Erro em solução assintótica de recorrência

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 (*).