Fenómeno

Mismo O, diez veces más lento

Dos programas suman un millón de números. Uno los tiene en un array; el otro, en una lista enlazada. Los dos hacen exactamente un millón de sumas y recorren todo una vez: O(n) los dos. El de la lista tarda varias veces más.

La notación O cuenta operaciones. No cuenta cuánto tarda cada una.

Piensa antes de seguir: ¿qué tiene que hacer el procesador para leer el siguiente valor de la lista que no tenga que hacer en el array?