Resolver la recurrencia $T(n)= 10 T\left(\frac{n}{100}\right)+ 100 n$ ?

Question

No consigo averiguar qué caso del teorema maestro debo utilizar aquí, cualquier sugerencia sería útil.

$ T(n)= 10 T\left(\frac{n}{100}\right) + 100 n$

Answer 1

Permítanme considerar el caso poco más general de la recurrencia, como ya me encontré con preguntas similares en este sitio, por lo que será más útil. Tomando $n=a^{2k}$ tenemos $$T(n)= a T\left(\frac{n}{a^2}\right) + a^2 n = a^2T\left(\frac{n}{a^4}\right)+\left[1+\frac{1}{a} \right]n a^2=\\ =a^3T\left(\frac{n}{a^6}\right)+\left[1+\frac{1}{a} +\frac{1}{a^2}\right]n a^2=\\ = \cdots =\\ =a^kT\left(\frac{n}{a^{2k}}\right)+\left[1+\frac{1}{a} +\frac{1}{a^2} +\cdots+ \frac{1}{a^{k-1}}\right]n a^2 = \\ =\sqrt{n}T(1)+\left[1+\frac{1}{a} +\frac{1}{a^2} +\cdots+ \frac{1}{a^{\log_a\sqrt{n}-1}}\right]n a^2$$ como, por ejemplo $a \gt 1$ suma parcial es convergente, entonces podemos obtener la estimación de $T(n)$ por $A\sqrt{n} +Bn$ para algunos $A,B$ constantes, que, por supuesto, es $\Theta(n)$ pero es más informativo.

Answer 2

Este es el "caso 3" del teorema maestro, aquel en el que se necesita la condición de regularidad en el término restante. $100n$ satisface la regularidad porque $af(n/b)=10n<50n=\frac12f(n)$ Así que $T(n)\in\Theta(n)$ .