Tienes que saber
- el algoritmo
- el camino más corto a través del algoritmo
- el camino más largo a través del algoritmo
- cómo varían las longitudes de la ruta o el número de iteraciones con el número de elementos de datos procesados
- cómo se ve un conjunto de datos "promedio".
La complejidad temporal del mejor caso se puede calcular considerando lo que sucede con el tiempo de ejecución o el número de iteraciones cuando aumenta el conjunto de datos en 1 elemento, en 2 elementos, en un factor de 2, un factor de 3. Si el tiempo de ejecución el aumento es lineal con el número de elementos de datos, decimos que la complejidad del tiempo es O (N), es decir, en el orden de N, el número de elementos de datos. Si el tiempo de ejecución varía como el cuadrado del número de elementos de datos, entonces decimos que la complejidad del tiempo es O (N
2 ). La complejidad del tiempo puede ser de otros órdenes, exponencial o tener alguna otra relación con el número de elementos de datos, por ejemplo, O (N
3/2 ).
Se puede realizar la misma evaluación de la complejidad del tiempo para los casos más desfavorables y medios.