Choisir constant pour la dernière étape du procédé de substitution $ T (n)= 5t (n / 4) + n ^ 2 $

Question

J'ai compris une solution à une relation de récurrence, mais je ne suis pas sûr de la constante de la constante pour la dernière étape.

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

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

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

panne

$ T (n) \ Leq 5 (n / 4) ^ 2) + n ^ 2 $

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

$ \ leq cn ^ 2 $

Pour la dernière étape pour tenir, je ne suis pas sûr de la valeur de C devrait être à cause du (5/16).Mon hypothèse serait C>= 1 et je ne suis pas sûr que cela tiendrait.

Answer 1

votre constante $ C $ doit satisfaire $$ \ frac {5} {16} c n ^ 2 + n ^ 2 \ Leq c n ^ 2, $$ C'est, $$ \ frac {5} {16} C + 1 \ Leq c.$$ J'espère que vous pourrez déterminer l'ensemble des constantes $ C $ C $ pour laquelle cette inégalité est satisfaite.

Answer 2

$$ t (n)= 5t \ gauche (\ frac {n} {4} \ droite) + n ^ 2= 5 ^ 2T \ gauche (\ frac {n} {4 ^ 2} \ droite) + \ Gauche (\ frac {5} {16} +1 \ droite) n ^ 2= \\= 5 ^ 3t \ gauche (\ frac {n} {4 ^ 3} \droite) + \ Gauche (\ Gauche (\ frac {5} {16} \ droite) ^ 2 + \ frac {5} {16} +1 \ droite) N ^ 2=CDOTS= \\ = 5 ^ kt \ gauche (\ frac {n} {4 ^ k} \ droite) + \ Gauche (\ gaucher (\ frac {5} {16} \ droite) ^ {k-1} + \ CDOTS + \ frac{5} {16} +1 \ droite) n ^ 2 $$ Si vous avez une condition initiale pour $ t (1) $ et nous supposons $ n= 4 ^ k \ leftrightRow k=\ log_ {4} n $ , alors nous obtenons $$ t (n)= 5 ^ kt (1) + n ^ 2 \ frac {16} {11} \ gauche (1- \ Gauche (\ frac {5} {16} \ droite) ^ {k-1} \ droite) \ in o (n ^ 2) $$