La complejidad temporal para el caso peor es igual a la cantidad máxima de nodos generados hasta un costo de formula_7 (costo óptimo), es decir, hasta una profundidad de formula_8, siendo formula_9 el costo más pequeño aplicable a una acción.