Nota: esto es de las notas de Algoritmos de JeffE sobre Recurrencias, página 5.
(1) Entonces definimos la recurrenciaSin ningún caso base. Ahora entiendo que para la mayoría de las recurrencias, dado que estamos buscando límites asintóticos, el caso base no importaría. Pero en este caso, ni siquiera veo dónde podríamos definir el caso base. ¿Hay algún número que tengamos éxito para garantizar que seguimos tomando raíces cuadradas a partir de cualquier número entero? para , para algunos reales , ?
(2) En la página 7, Erickson entiende que la cantidad de capas en el árbol de recursión L satisfará. ¿De dónde viene esto? No tengo idea. Veo que el número de hojas en el árbol debería sumar, pero no tengo idea de a dónde ir desde allí.
Cualquier ayuda es apreciada!
Notas que estoy viendo: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf
fuente