Puede ' t resolver una repetición

Question

Estoy tratando de resolver el siguiente recurrencia:

$$T(n) = 9T(n/3)+n^2$$

Si yo uso el maestro método, I se $n^2\log{n}$

Pero, estoy tratando de resolverlo por medio de la sustitución. Cuando trato de resolverlo de esta manera, sin embargo, me encuentro en problemas. Después de que yo el rollo de la sustitución de un par de veces, tengo la siguiente fórmula:

$$T(n) = 9^kT(n/3^k)+n^2\sum_{i=1}^k3^{j-1}$$

He tratado de simplificar la suma de varias maneras, pero creo que no estoy entendiendo lo que el siguiente paso debe ser. Cuando me simplificar el problema, sigo recibiendo la respuesta equivocada. Sé que debería finalmente a las $k$, lo que equivale a unos logaritmo así que un llegar a la base de caso por T, pero ahora mi principal problema es averiguar cómo simplificar la suma. Soy bastante mala en la simplificación de sumatorias, por lo que cualquier detalle los pasos son muy apreciados.

Answer 1

Su suma está mal. Debe ser

$$T(n) = 9^k T(n / 3^k)+ \sum_{i=1}^k n^2$$

Esto es porque $(n / 3^k)^2 = n^2 / 9^k$ para que pueda obtener cancelaciones.

Answer 2

La suma parece especialmente "bonita" si $n$ es un poder de $3$, que permite asume $n=3^k$, entonces el $$T(3^k)=3^2T(3^{k-1})+3^{2k}$ $ y$$ T(3^{k-1})=3^2T(3^{k-2})+3^{2k-2} lo susbstitution: $$T(3^k)=3^2(3^2T(3^{k-2})+3^{2k-2})+3^{2k}=3^4T(3^{k-2})+23^{2k} ahora, $$T(3^{k-2})=3^2T(3^{k-3})+3^{2k-4}$$ So $$T(3^k)=3^4(3^2T(3^{k-3})+3^{2k-4})+23^{2k}=3^6T(3^{k-3})+33^{2k} en general $$T(3^k)=3^{2a}T(3^{k-a})+a3^{2k} $$for any natrual $ $ (can be easily verified via induction), so if we set $ un = k$, conseguimos$$ T(3^k)=3^{2k}T(1)+k*3^{2k} ahora sustituyendo al revés $k=\log_3(n)$, conseguir que $$T(n)=n^2T(1)+n^2\log_3(n)

Answer 3

$$T(n)-9T(n/3)=n^2$$ $$9^kT(n)-9^{k+1}T(n/3)=9^kn^2$$ $$9^kT(n/3^k)-9^{k+1}T(n/3^{k+1})=n^2$$ $$\sum_{k=0}^{\lfloor{\log_3(n)}\rfloor}9^kT(n/3^k)-9^{k+1}T(n/3^{k+1})=n^2(\lfloor{\log_3(n)}\rfloor+1)$$ $$T(n)-9T(n/3)+9T(n/3)-9^2T(n/3^2)+....-9^{\lfloor{\log_3(n)}\rfloor}T(n/3^{\lfloor{\log_3(n)}\rfloor})=n^2(\lfloor{\log_3(n)}\rfloor+1)$$ $$T(n)=n^2(\lfloor{\log_3(n)}\rfloor+1)+9^{\lfloor{\log_3(n)}\rfloor}T(n/3^{\lfloor{\log_3(n)}\rfloor})$$ $$=n^2\log_3(n)+O(n^2T(n/3^{\lfloor{\log_3(n)}\rfloor}))$$ $$=n^2\log_3(n)+O(n^2T(c))$$ $$\text{Where } 0<c></c>