Proving construir um BST balanceado de matriz classificado é $ \ theta (n) $

Question

Eu estou tendo dificuldade em provar construir uma BST Balanced fora de matriz classificada é $ \ theta (n) $

Eu recebi a seguinte fórmula: $$ T (n)= 2T (\ Frac {n} {2} {2}) + \ theta (1) $$ .

Eu tentei provar por indução, mas fiquei preso com o caso em que $ n $ é um número ímpar.

Existe uma maneira melhor de provar isso?Substituição não seria considerada uma prova válida (cheguei à fórmula fechada usando substituição de curso).

Answer 1

Se você tiver permissão para usar o Teorema Master Então você pode concluir imediatamente que $ t (n)=theta (n) $ (já que $ n ^ {\ log_2 2}= n=ômega (1) $ ).

Se você não tem permissão para usar o Teorema Master, então você pode escrever esta recorrência: $$ T (n) \ le 2t (\ LFLOOR N / 2 \ RFLOOR) + C, $$ onde $ c> 0 $ é uma constante absoluta e $ t (1) \ le C $ . < / p >.

Então você pode provar por indução que $ t (n) \ le 2cn - C $ . O caso da base é $ n= 1 $ e é trivial desde $ t (1) \ le c= 2cn - C $ . Considere agora $ n> 1 $ e suponha que a reivindicação mantenha até $ N-1 $ , nós provará que também é válido para $ n $ : $$ T (n)= 2t (\ lFloor n / 2 \ rfloor) + c \ le 2 (2C \ lFloor n / 2 \ rfloor-c) + c \ le 2CN - 2C + C= 2CN-c. $$