Límite superior para $T(n) = T(n - 1) + T(n/2) + n$ con árbol de recursión

Question

Estoy leyendo Introducción a Algoritmos, 3ª ed. y me quedé atascado en la siguiente recurrencia (ejercicio 4.4-5):

$$T(n) = T(n - 1) + T(n/2) + n$$

El ejercicio te pide que encuentres el límite superior utilizando el método del árbol de recurrencia. He intentado dibujar uno. Habría $2^n$ hojas si fuera un árbol binario completo (la altura es $n$ ), pero no lo es. Además, no encuentro una fórmula que exprese la complejidad de cada nivel como lo hacen en el libro.

Después de escribir algo de código para calcular $T(n)$ y comparándolo con diferentes funciones, acabo pensando que la complejidad es exponencial. Utilizando $c2^n$ con el método de sustitución funciona, pero no estoy seguro de que esto sea un límite estricto. Tampoco estoy seguro de que el límite ajustado sea exponencial.

¿Puede alguien ayudarme con el razonamiento?

P.D.: Si importa, no estoy en la escuela/universidad y esto no es una tarea. Soy un programador (digamos) de Ruby que está estudiando por su cuenta para llenar sus lagunas en Informática.

Answer 1

Acabo pensando que la complejidad es exponencial.

No es así.

Una respuesta anterior afirmaba correctamente que $T(n)\geqslant\frac12n^2$ y erróneamente que la propiedad $T(n)\leqslant cn^2$ es hereditaria (es decir, si se mantiene para cada $k\leqslant n-1$ se mantiene para $n$ ) para cada $c\geqslant2$ .

De hecho, la propiedad $T(n)\leqslant cn^2$ es no hereditaria y la complejidad no es ni polinómica ni exponencial. Parece que $\log T(n)\sim(\log n)^2/(2\log2)$ y probablemente se pueda comprobar que, por cada positivo $\varepsilon$ la propiedad $$ \exp((\log n)^{2-\varepsilon})\leqslant T(n)\leqslant\exp((\log n)^{2+\varepsilon}) $$ es hereditaria para cada $n$ lo suficientemente grande.