Resolvendo a relação de recorrência

Resolvendo a relação de recorrência . O livro do qual este exemplo é afirma falsamente que adivinhando e depois argumentando $T(n) = 2T(\lfloor n/2 \rfloor) + n$
$T(n) = O(n)$$T(n) \leq cn$

$\qquad \begin{align*} T(n) & \leq 2(c \lfloor n/2 \rfloor ) + n \\ &\leq cn +n \\ &=O(n) \quad \quad \quad \longleftarrow \text{ wrong!!} \end{align*}$

uma vez que é constante. O erro é que não provamos a forma exata da hipótese indutiva.$c$

Acima, citei exatamente o que o livro diz. Agora, minha pergunta é por que não podemos escrever onde e agora temos e, portanto, ?$cn+n=dn$$d=c+1$$T(n) \leq dn$$T(n) = O(n)$

Nota:

1. A resposta correta é$T(n) =O(n \log n).$
2. O livro que estou me referindo aqui é Introdução aos algoritmos de Cormen et al., Página 86, 3ª edição.

Os autores dão a resposta:

O erro é que não provamos a forma exata da hipótese indutiva, ou seja, que .$T(n) \leq cn$

É verdade que isso é difícil de entender se você não está acostumado a fazer induções (certo), porque elas não fazem a indução explícita / rigorosamente. Em resumo: você precisa ter uma constante para todos os , mas essa (des) prova constrói muitos (um por ).$c$$n$$n$

Por muito tempo, lembre-se do que significa:$T(n) \in O(n)$

$\qquad \displaystyle \exists c \in \mathbb{N}.\, \exists n_0 \in \mathbb{N}.\, \forall n \geq n_0.\, T(n) \leq cn$

ou equivalente,

$\qquad \displaystyle \exists c \in \mathbb{N}.\, \forall n \in \mathbb{N} T(n) \leq cn$ .

A segunda forma funciona melhor para uma indução, como você conhece a âncora. Então você precisa de uma constante que forneça um limite superior para todos os .$c$ $n$

Vamos inspecionar o que a indução faz:

• Âncora de indução: a âncora de não é explicitamente dada, mas é constante, portanto, encontramos um adequado .$T$$c$
• Hipótese de indução: Há alguns para que para todos os , para alguns arbitrários mas fixos .$c$$T(k) \leq cn$$k\leq n$$n$
• Etapa indutiva: como mostrado na pergunta, construa para que .$d > c$$T(n+1) \leq dn$

Então, com efeito, construímos uma nova constante para cada . Isso não se encaixa na definição de ! E, pior, é completamente sem sentido: toda função pode ser "delimitada" por qualquer outra função se você puder ajustar o fator com .$n$$O$$n$

Em relação à prova de indução, deve fazer parte da reivindicação (e é, oculta no ), que está ligada "fora" da indução. Então, o mesmo aparece em âncora, hipótese e passo. Veja a última parte desta resposta para um exemplo.$c$$O$$c$