Para medir la eficiencia de los algoritmos se usará el principio de invariancia que establece la eficiencia de dos implementaciones diferentes de un mismo algoritmo que difieren solamente en una constante multiplicativa. A medida que crece el tamaño de un algoritmo de un programa generalmente crece el tiempo de ejecución, determinando la tasa de crecimiento del programa o algoritmo.
Las consideraciones de eficiencia son: el tiempo y el espacio. Siendo importante la cantidad de tiempo para ordenar un archivo. La eficiencia de una solución a un problema es cuando su tiempo de ejecución se encuentra dentro de los límites de una función polinomial es decir Q(nk); es decir, si está entre este rango se considera fácil; de lo contrario, es difícil.
Para determinar las unidades de tiempo de ejecución de un algoritmo se debe utilizar una función T(n) para cualquier entrada. Un programa puede tener un tiempo T(n)=cn donde c>0 es una constante, por lo tanto, el tiempo de ejecución de un programa es linealmente proporcional al tamaño de la entrada sobre la que se ejecuta. T(n) es el número de sentencias ejecutadas en un algoritmo en un tiempo dado. Con frecuencia, el tiempo de ejecución de un programa depende de una entrada y no del tamaño del algoritmo. Tmedia(n) es el tiempo medio de ejecución del programa sobre todas las entradas de tamaño n, pero esta media es poco aceptable debido a que todas las entradas de tamaño n son igualmente probables.
La clasificación de tiempos de ejecución de más rápido a más lentos así:
Donde n es la entrada y k una constante. Su medición de tiempo de ejecución se hace por: