Editing Iterative deepening depth-first search (section)

=== Space complexity ===

The [[space complexity]] of IDDFS is <math>O(d)</math>,<ref name="re1985"/>{{rp|5}} where <math>d</math> is the depth of the goal.

==== Proof ====

Since IDDFS, at any point, is engaged in a depth-first search, it need only store a stack of nodes which represents the branch of the tree it is expanding. Since it finds a solution of optimal length, the maximum depth of this stack is <math>d</math>, and hence the maximum amount of space is <math>O(d)</math>.

In general, iterative deepening is the preferred search method when there is a large search space and the depth of the solution is not known.<ref name="rn3"/>