Ya sabemos como acotar el tiempo de un algoritmo, pero también nos interesa saber si este tiempo es eficiente. Desde un punto de vista práctico, si en una competencia corre dentro del tiempo límite estipulado podemos decir que es eficiente. Esta no es una respuesta que resulte de utilidad en cualquier otro caso, por lo que es conveniente encontrar otra.
En general, se considera que la solución de un problema es eficiente si el tiempo de ejecución está acotado por una función polinomial, es decir, por O(nk). A este tipo de se le considera un problema fácil. En caso de que su tiempo de ejecución sea mayor, se le considera difícil. Para saber si un problema es fácil, sólo debemos encontrar un algoritmo que lo resuelva en forma rápida. Para saber si un problema es difícil no basta con encontrar un algoritmo que no sea eficiente, sino que tenemos que demostrar que no existe algoritmo que lo resuelva de forma fácil. Dado que todo problema que no es fácil lo consideramos difícil, cualquier problema que se compruebe que es imposible de solucionar entra en la última categoría.
Los tiempos de ejecución más usados se ordenan de la siguiente forma (de más rápidos a más lentos): O(1) (constante), O(lgn) (logarítmico), O([lgn]k) (polilogarítmico), O(n) (lineal), O(nlgn), O(n2) (cuadrado), O(n3) (cúbico), O(nk) (polinomial), O(kn) (exponencial), O(nn) y O(n!) (factorial) donde n es la entrada y k una constante.
Aún así, hay que tomar en cuenta que esto indica la cantidad de operaciones que el algoritmo realizará ante una entrada n, por lo que un algoritmo O(cn3) puede ser más rápido para algunas entradas que uno O(cn2) si consideramos el tiempo de hacer las operaciones del primero es menor que las del segundo (la constante del primero es menor que la del segundo). Por ejemplo: si tenemos O(5n3) y O(100n2), entonces para valores de n menores que 20 el primer algoritmo será más rápido.
En la siguiente gráfica y tabla podemos ver como se comporta el crecimiento de algunas funciones (por el tamaño de n, no necesariamente están en el orden que se acaban de mencionar):
 |
| Figura 2.2: Comparación del crecimiento de algunas funciones comunes. (Nota: por el rango de n, algunas funciones no están completamente ordenadas.) |
| 1 | lg(n) | n | nlg(n) | n2 | n3 | 2n | n! | |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 | 1 | 1 | 2 | 1 |
| 2 | 1 | 1 | 2 | 2 | 4 | 8 | 4 | 2 |
| 4 | 1 | 2 | 4 | 8 | 16 | 64 | 16 | 24 |
| 8 | 1 | 3 | 8 | 24 | 64 | 29 | 256 | ≈ 4×104 |
| 16 | 1 | 4 | 16 | 64 | 256 | 212 | ≈ 6×104 | ≈ 2×1013 |
| 32 | 1 | 5 | 25 | 160 | 210 | 215 | ≈ 4×109 | ≈ 8×1033 |
| 210 ≈ 103 | 1 | 10 | 210 | ≈ 104 | 220 | 230 | ≈ 10308 | ≈ 102639 |
| 220 ≈ 106 | 1 | 20 | 220 | ≈ 2×107 | 240 | 260 | - | - |
| 230 ≈ 109 | 1 | 30 | 230 | ≈ 3×1010 | 260 | 290 | - | - |
| 240 ≈ 1012 | 1 | 40 | 240 | ≈ 4×1013 | 280 | 2120 | - | - |
| 250 ≈ 1015 | 1 | 50 | 250 | ≈ 5×1016 | 2100 | 2150 | - | - |
Cotas de complejidad
