O(n*log(n)) versus O(n^2)

Este es un ejemplo de como perjudica al tiempo de cálculo la complejidad temporal. Supongamos tener dos algoritmos para ordenar una lista de objetos, uno simple con costo O(n^2) (1) y otro complejo con consto O(n*log(n)) (2). Supongamos tener una super computadora que ejecuta 10^8 operaciones por segundo, le programamos el algoritmo (1) para que ordene n datos. Y tenemos una computadora vieja que realiza 10^6 operaciones por segundo, le programamos el algoritmo (2) para que ordene también los n datos. Luego para ordenar 1 millón de datos la super computadora tardará

t=(10^6)^2/10^8=10000 segundos ó aproximadamente 2,7 horas.

en cambio la computadora vieja tardará

t=10^6*log(10^6)/10^6=13,81 segundos.

Saque usted sus propias conclusiones ….