PUERTA | PUERTA CS 2020 | Pregunta 26

¿Cuál es la complejidad de tiempo en el peor de los casos de insertar n elementos en una lista enlazada vacía, si la lista enlazada necesita mantenerse ordenada?
(A) Θ(n)
(B) Θ(n log n)
(C) Θ(n ² )
(D) Θ(1)

Respuesta: (C)
Explicación: Esta pregunta es ambigua: “necesita mantenerse ordenada orden”, hay dos casos posibles:

1. Debe mantenerse ordenado en cada paso (después de cada inserción) .
   Cuando estamos insertando un elemento en una lista enlazada vacía y para realizar una lista ordenada de cada elemento, tomará O (n ² ).
   Cada inserción en una lista enlazada ordenada tomará θ(n) y, por lo tanto, el costo total para n operaciones es θ(n ² ).
2. Debe mantenerse ordenado en el paso final (solo después de todas las inserciones) .
   Cuando estamos insertando todos los elementos en una lista enlazada vacía y para realizar una lista ordenada ( usando la ordenación por fusión ) después de insertar todos los elementos tomará tiempo O (n log n).

La respuesta oficial de GATE es Θ(n ² ).

Cuestionario de esta pregunta