Consultas 2022

Hola,

El error está en sumar el tamaño de los problemas en vez de la cota del tiempo de ejecución de cada uno.

En general, para obtener una cota al tiempo de ejecución $T(n)$ sumando todos los niveles de la recursión lo que hay que sumar es el tiempo de ejecución de todos los subproblemas. En este caso, como bien dijiste, en el nivel $j$ de la recursión son $2^j$ problemas con tiempo de ejecución acotado por una constante $c$ (independientemente del tamaño de los subproblemas).

Sumando en todos los niveles se obtiene $T(n) \leq \sum_{j=0}^{\log(n)-1} 2^j c = c (2^{\log(n)} - 1) \leq c n = O(n)$.

Saludos,

Tatiana