Resolver las recurrencias $T(n) = 4 T(2n/3) + (n^3 )\cdot \log(n)$

Question

Tengo una recurrencia: $T(n) = 4 \cdot T\left(\frac{2n}{3}\right) + (n^3 )\cdot \log(n)$

cómo se puede resolver este caso a partir del teorema maestro ya que éste no está en la forma general de $T(n) = aT(n/b) + O(nd)$

Answer 1

Tienes razón en que esto se puede resolver a través del Teorema Maestro, aunque probablemente no con la versión que conoces. Esta versión del Teorema Maestro es más general y afirma, en parte, que si se tiene una recurrencia de la forma $$T(n)=aT(n/b)+f(n)$$ con $a\ge 1, b>1$ (que tenemos, ya que $a=4\ge1$ y $b=(3/2)>1$ ) entonces si hay una constante $\epsilon>0$ para lo cual $$f(n)=O(n^{\log_b a -\epsilon})$$ entonces $T(n) = \Theta(n^{\log_b a})$ .

Para ver que este es el caso que nos interesa, observa que $\log_{3/2}4\approx3.419$ así que si podemos establecer que hay una $\epsilon>0$ tal que $$f(n) = n^3\log n = O(n^{\log_b a -\epsilon})$$ entonces se deduce que $T(n) = \Theta(n^{\log_{3/2} 4})$ .

Supongo que sabes que $\log n$ crece asintóticamente más lento que y potencia positiva de $n$ lo que significa que para cualquier $\alpha >0$ tendremos $\log n=O(n^\alpha)$ así que $$n^3\log n=O(n^{3+\alpha})$$ Sin ninguna razón en particular, tomaremos $\alpha = 0.4$ entonces tendremos $n^3\log n=O(n^{3.4})$ y así tendremos $$f(n)=O(n^{3.4}) = O(n^{3.419-.019})=O(n^{\log_{3/2} 4-\epsilon})$$ para $\epsilon\approx 0.019$ . Las condiciones de este caso del Teorema Maestro se satisfacen, por lo que $$T(n)=\Theta(n^{\log_{3/2}4})$$

Answer 2

Pruebe la sustitución $n=(\frac{3}{2})^{u}$