Qué caso del teorema de Master se aplica a la recurrencia $T(n)= 100T(n/99)+\log(n!)$ ?

Question

Cómo utilizar el teorema de Master para resolver $T(n)= 100T(n/99)+\log(n!)$ ?

Me han hecho esta pregunta y no consigo averiguar qué caso del teorema maestro va aquí. Gracias por vuestras sugerencias.

Answer 1

Recuérdalo: $$ \log(n!) \leq \log(n^n) = n\log n = O(n^k) $$ para cualquier $k > 1$ . Así, puesto que $\log(n!) = O(n^{(\log_{99}100) - \epsilon})$ para cualquier $\epsilon \in (0, (\log_{99} 100) - 1)$ por el caso $1$ del Teorema Maestro que: $$ T(n) = \Theta(n^{\log_{99} 100}) $$