We analyze the computational complexity of the search algorithm called
"Iterative-Deepening-A*" used in artificial intelligence,
under some modest hypotheses.
Our theoretical predictions, which are asymptotic,
are shown to match the empirically observed behavior of the algorithm,
even in relatively small searches.