Eligiendo constante para el último paso en el método de sustitución $ t (n)= 5T (N / 4) + N ^ 2 $

Question

Me di cuenta de una solución a una relación de recurrencia, pero no estoy seguro de cuál debería ser la constante para que lo sostenga el último paso.

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

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

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

Desglose

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

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

$ \ leq cn ^ 2 $

Para el último paso para mantener, no estoy seguro de cuál debe ser el valor de C debido a la (5/16).Mi conjetura sería C>= 1 y no estoy seguro de si eso se sostendría.

Answer 1

su constante $ C $ necesita para satisfacer $$ \ FRAC {5} {16} C N ^ 2 + N ^ 2 \ leq C n ^ 2, $$ es decir, $$ \ frac {5} {16} C + 1 \ leq c.$$ Esperemos que pueda determinar el conjunto de constantes $ c $ por lo que esta desigualdad está satisfecha.

Answer 2

$$ t (n)= 5t \ izquierda (\ frac {n} {4} \ derecha) + n ^ 2= 5 ^ 2t \ izquierda (\ frac {n} {4 ^ 2} \ justo a la derecha) + \ izquierda (\ frac {5} {16} +1 \ derecha) N ^ 2= \\= 5 ^ 3T \ IZQUIERDA (\ frac {n} {4 ^ 3} \derecha) + \ \ a la izquierda (\ \ \ frac {5} {16} \ derecha) ^ 2 + \ frac {5} {16} +1 \ derecha) N ^ 2=cdots= \\ = 5 ^ kt \ izquierda (\ frac {n} {4 ^ k} \ derecha) + \ izquierda (\ \ \ \ frac {5} {16} \ derecha) ^ {k-1} + \ cdots + \ frac{5} {16} +1 \ derecha) N ^ 2 $$ Si tiene alguna condición inicial para $ t (1) $ y asumimos $ n= 4 ^ k \ leftrightarrow k=\ log_ {4} n $ , entonces obtenemos $$ t (n)= 5 ^ kt (1) + n ^ 2 \ frac {16} {11} \ izquierda (1- \ \ \ \ \ frac {5} {16} \ Derecha) ^ {K-1} \ Derecha) \ In O (n ^ 2) $$