Time and Space Complexity

Complejidad Temporal:

• Mejor Caso: O(n)
  • Cuando el arreglo ya está ordenado, Insertion Sort realiza solo una pasada para confirmar el orden ordenado.
• Caso Promedio y Peor Caso: O(n²)
  • En los casos promedio y peor, toma tiempo cuadrático porque, para cada elemento, es posible que necesitemos comparar y desplazar a través de toda la porción ordenada.

Complejidad Espacial:

• O(1)
  • Insertion Sort es un algoritmo "in-place" (en el lugar), lo que significa que no requiere memoria adicional proporcional al tamaño de la entrada.
  • El espacio utilizado para la ordenación permanece constante, independientemente del tamaño de la entrada.

Resumen:

• Insertion Sort es eficiente para conjuntos de datos pequeños o arreglos casi ordenados.
• Es menos adecuado para conjuntos de datos grandes debido a su complejidad temporal cuadrática.
• La complejidad espacial es constante, lo que lo hace eficiente en memoria para cualquier tamaño de entrada.