Ejercicio 2)b) - Primer Parcial 2018

Ejercicio 2)b) - Primer Parcial 2018

de Bruno Emanuel Gandos Telis -
Número de respuestas: 1

Hola, en este ejercicio quise demostrar el orden "desarmando la recurrencia" como lo hacen en el libro, pero me surgió un problema.

1

Obtuve un tiempo de ejecución O(nlog(n)) lo cual es incorrecto, podrían decirme cual fue mi error? Gracias.

En respuesta a Bruno Emanuel Gandos Telis

Re: Ejercicio 2)b) - Primer Parcial 2018

de Tatiana Rischewski Santomauro -

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