Nota: esto es de JeffE, los Algoritmos de notas en las Recurrencias, página 5:
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf
(1). Entonces definimos la recurrencia $T(n) = \sqrt{n}T(\sqrt{n})+n$ sin ningún tipo de caso base. Ahora entiendo que para la mayoría de las recurrencias, ya que estamos buscando para asintótica de los límites, el caso base no importaría. Pero en este caso, no quiero ni ver dónde podríamos definir el caso base. ¿Hay algún número que están garantizados para golpear como seguimos tomando raíces cuadradas a partir de cualquier número entero no acabamos de definir $T(n) = a$$n<b$, por unos pocos reales $a$, $b$?
(2). En la página 7, Erickson obtiene que el número de capas en la recursividad del árbol de L va a satisfacer $n^{{2}^{-L}} = 2$. Donde se esta viniendo? Yo no tengo ni idea. Veo que el número de hojas en cada nivel del árbol deben suma a $\sqrt(n)\sqrt(n) = n$, pero no tengo idea de a dónde ir desde allí.
(3). A partir del resultado mencionado en (2). Erickson se deriva $T(n) = \theta(n\lg\lg(n))$. Pero desenrollar la recurrencia de los rendimientos $$T(n) = n^{\sum\limits_{i=1}^k \frac{1}{2^{i}}}T(n^{\frac{1}{2^k}})+kn \leq (k+1)n $$
Para cualquier entero k. No significa esto $T(n) = O(n)$, contradiciendo $T(n) = \theta(n\lg \lg(n)$? Dónde está mi razonamiento equivocado? (Por favor, sepan que hago con la completa confianza de que está mal).
Esto también está publicado en la ciencia de la computación de intercambio de la pila, debido a la superposición de temas.
Cualquier ayuda es muy apreciada.
