¿Cómo resolver la relación de recurrencia para el límite asintótico ajustado sin utilizar el teorema maestro?

Question

Tengo la siguiente recurrencia en mi problema: $$T(n)= 4T(n/2)+n.$$
Lo he resuelto por sustitución asumiendo el límite superior $O(n^3)$ pero al resolverlo para $O(n^2)$ Estoy teniendo algunos problemas.Sé que este problema está más limitado a $O(n^2)$ . A continuación, los intentos realizados por mí a través de la inducción:

Supongamos que $$T(k)\leqslant ck^2, \mbox{ for } k.$$ Ahora tenemos
$$T(n)=4T(n/2)+n,$$ $$T(n)=4c(n^2/4)+n, \mbox{ from induction hypothesis as } n/2<n,$$ $$\ldots$$ $$T(n)=cn^2+n.$$

Así que al final, si tengo que probar este límite estricto, el requisito se convierte en

$$cn^2 + n \leqslant cn^2.$$
Ahora no entiendo cómo salir de esto con la inducción no utilizando el teorema maestro? Soy un principiante en esto así que por favor perdonen si he producido algún error sintáctico. Gracias de antemano.

Answer 1

El llamado teorema maestro no es necesario de todos modos, ni aquí ni en muchas otras preguntas de la misma índole que se hacen en math.se, así que el hecho de que requieras una solución que no lo utilice es bastante bienvenido... Aquí vamos:

Al igual que cuando se estudian las ecuaciones diferenciales ordinarias, se parte de la parte lineal de la relación, es decir, $$T(n)=4T(n/2)=\color{blue}{2}^{\color{red}{2}}T(n/\color{blue}{2}),$$ o de forma equivalente, $$\frac{T(n)}{n^{\color{red}{2}}}=\frac{T(n/2)}{(n/2)^{\color{red}{2}}},$$ que obviamente se resuelve con $$T(n)=Cn^{\color{red}{2}},$$ para alguna constante $C$ . Esto sugiere transformar la relación en cuestión, utilizando $$S(n)=T(n)/n^2.$$ Se obtiene $$S(n)=S(n/2)+1/n.$$ Mejor, pero no la mejor formulación posible... Iterando la identidad que implica $S$ produce los valores de $S$ en $n/2$ , $n/4$ y así sucesivamente, por lo que también podríamos considerar desde el principio $$R(k)=S(2^k)=T(2^k)/4^k.$$ Ahora la relación en cuestión se convierte en $$R(k)=R(k-1)+1/2^k,$$ es decir, $$R(k)=R(0)+1/2+1/4+\cdots+1/2^k=R(0)+1-1/2^k,$$ o de forma equivalente, $$T(2^k)=4^k(T(1)+1)-2^k,$$ lo que demuestra que $$T(2^k)=\Theta(4^k),$$ para cada no negativo $T(1)$ . Y ahora viene una de las prácticas más insatisfactorias del campo, que es pretender que esta última identidad implica que $$T(n)=\Theta(n^2),$$ aunque no lo hace (y de todos modos, cuál sería la identidad de la que partimos cuando $n=3$ ?).

En retrospectiva, la fórmula exacta que encontramos sugiere que el límite superior $$T(n)\leqslant Cn^2-n,$$ debería pasar fácilmente. Y si este límite superior se mantiene para $n/2$ entonces $$T(n)=4T(n/2)+n\leqslant4(C(n/2)^2-(n/2))+n=Cn^2-n,$$ como se desee. Asimismo, todo límite inferior $$T(n)\geqslant cn^2-n,$$ es hereditaria.

Answer 2

Si $n=2^k$ entonces la recurrencia $$T(n)=4T(n/2)+n,$$ se convierte en $$ T\big(2^{k}\big)=4T\big(2^{k-1}\big)+2^k, $$ y por lo tanto, si establecemos $S(k)=T\big(2^k\big)$ entonces $S(k)$ satisface la relación de recurrencia $$ S(k)=4S(k-1)+2^k, $$ y por lo tanto $$ \frac{S(k)}{4^k}=\frac{S(k-1)}{4^{k-1}}+2^{-k}. $$ Así, $$ \frac{S(k)}{4^k}=2^{-k}+2^{-k+1}+\cdots+2^{-1}+S(0)=S(0)+1-\frac{1}{2^k}, $$ y en consecuencia $$ S(k)=4^k\big(S(0)+1\big)-2^k, $$ y por último, sustituyendo de nuevo $n=2^k$ y $S(k)=T(n)$ obtenemos $$ T(n)=n^2\big(T(1)+1\big)-n. $$