Ejercicio 8

Ejercicio 8

de Agustín Arístides Almeida Ahlers -
Número de respuestas: 1

Buenas noches,

Tengo varias dudas para resolver este ejercicio. En primer lugar, para la parte a, debo analizar el orden del algoritmo sin asumir ningún orden? O sea, suponiendo que remover el mínimo es O(1) podría afirmar que es O(n) por dar un ejemplo. Luego, para la parte b y c no me queda claro si es O(n) que esto implique que \Omega (n) también. Debería asumir que el mejor caso también es de orden n? Supongo que tanto en b como en c puedo concluir que el algoritmo es O(n^2) y O(n*log n) respectivamente pero no podría afirmar nada sobre \Omega y \Theta . Espero se comprendan mis dudas, desde ya gracias,

Saludos.
En respuesta a Agustín Arístides Almeida Ahlers

Re: Ejercicio 8

de Libertad Tansini -
Hola Agustín,
en la parte a) sin suponer que removerMinimo es O(1), sabemos que el for se realiza n/2 veces siempre, por lo que resulta que T(n) es Ω(n), pero no podemos afirmar nada sobre O(n). Si removerMinimo fuera O(1) podríamos afirmar que T(n) es O(n) y por lo tanto también Θ(n).

En la parte b) asumiendo que removerMinimo es O(n), como hay Θ(n) iteraciones sólo podemos afirmar que T(n) es O(n^2).

En la parte c) T(n) es O(n log n).

saludos