Escolhendo constante para o último passo no método de substituição $ t (n)= 5T (n / 4) + n ^ 2 $

Question

Eu descobri uma solução para uma relação de recorrência, mas não tenho certeza do que a constante deve ser para o último passo para segurar.

$ t (n)= 5T (n / 4) + n ^ 2 $

Adivinha: $ t (n)= o (n ^ 2) $

Prove: $ t (n) \ leq cn ^ 2 $

avaria

$ t (n) \ leq 5 (c (n / 4) ^ 2) + n ^ 2 $

$= (5/16) CN ^ 2 + n ^ 2 $

$ \ leq cn ^ 2 $

Para o último passo para segurar, não tenho certeza qual o valor de C deve ser por causa do (5/16).Meu palpite seria c> 1 e não tenho certeza se isso seguraria.

Answer 1

sua constante $ c $ precisa satisfazer $$ \ frac {5} {16} c n ^ 2 + n ^ 2 \ leq c n ^ 2, $$ isso é, $$ \ frac {5} {16} c + 1 \ leq c.$$ Espero que você possa determinar o conjunto de constantes $ c $ para o qual esta desigualdade é satisfeita.

Answer 2

$$ t (n)= 5t \ left (\ frac {n} {4} \ direito) + n ^ 2= 5 ^ 2t \ esquerda (\ frac {n} {4 ^ 2} \ direito) + \ left (\ frac {5} {16} +1 \ direito) n ^ 2= \\= 5 ^ 3T \ left (\ frac {n} {4}} \direito) + \ \ left (\ esquerda (\ frac {5} {16} \ 8 + \ frac {5} {16} +1 \ direito) n ^ 2=cdoots= \\ = 5 ^ kt \ left (\ frac {n} {4 ^ k} \ direito) + \ left (\ left (\ frac {5} {16} \ \ {k-1} + \ cdots + \ frac{5} {16} +1 \ direito) n ^ 2 $$ Se você tiver alguma condição inicial para $ t (1) $ e nós assumimos $ n= 4 ^ k \ leftrightarrow k=\ log_ {4} n $ , então obtemos $$ t (n)= 5 ^ kt (1) + n ^ 2 \ frac {16} {11} \ left (1- \ left (\ frac {5} {16} \ direito) ^ {k-1} \ direito) \ in O (n ^ 2) $$