Tema 9 - TAD Colecciones III: TAD Cola de Prioridad

Hola.

El análisis que hiciste según el cual el algoritmo es $O(n \log n)$ puede ser correcto. Pero también puede ocurrir que se pueda hacer un análisis más detallado con el cual se llegue a que también es $O(n)$ (recordemos que estamos hablando de orden $O$, no de $\Theta$).

El análisis que hiciste tal vez fue que se aplica $O(n)$ veces el filtrado descendente, que es $O(\log n)$ en peor caso. ¿Puede ser? Eso estaría bien.

Pero en el análisis más detallado se tiene en cuenta que ese orden para el filtrado descendente corresponde a los casos en que se aplica a nodos cercanos a la raíz. Si el nodo está en los niveles más profundos, entonces el filtrado descendente sería $O(1)$. Como hay muchos más nodos en los niveles más profundos que cercanos a la raíz se puede llegar a demostrar que el algoritmo es $O(n)$.

¿Esto va bien encaminado para aclarar la duda?