Para evitar caer en caminos de profunidad muy grande, a la mayoría de los algortimos que usan depth-first se les impone un límite de profundidad máxima.
Si se sabe la profundidad de alguna meta, el algoritmo puede ser
completo, pero sigue sin ser óptimo. Si la profunidad es 
, se
tarda 
y ocupa 
.
Cuando se tienen grafos altamente conectados hay que tener cuidado con el concepto de profundidad (una más que el padre menos profundo). Por lo que en este caso, se tienen que analizar todos los padres, lo cual implica requerimientos adicionales de memoria.
En la práctica se puede tomar solo la profundidad del padre que lo generó haciendo una estrategia LIFO más ``pura''.