Coste

Construir: uno a uno o de una vez

Hay dos formas de construir el array ordenado con n pares: insertarlos uno a uno, manteniendo el orden, o cargarlos todos y ordenar una vez.

¿Cuánto cuesta cada forma de construir un array ordenado de n pares, en el peor caso?Uno a uno: O(n). Ordenar una vez: O(n log n), porque ordenar es una operación más generalLas dos O(n²), porque ordenar compara cada par de claves con todas las demásUno a uno: O(n²). Ordenar una vez: O(n log n)Las dos O(n log n), porque cada inserción busca su sitio en O(log n)