Next: Avoiding Repeated States Previous: Examples

Analysis

Time complexity
In the worst case, have to search entire search space
Solution may be at level , but tree may go to level , $m \;>=\; d$ , so run time is $O(b^m)$
Particularly bad if tree is infinitely deep

Space complexity
Only have to save 1 set of children at each level
$1 \;+\; b \;+\; b \;+\; \ldots \;+\; b$ ( levels total) = $O(bm)$

For previous case, DFS requires 118 kilobytes instead of 10 petabytes at d=12 (10 billion times less)

May not always find solution
Solution it finds is not always least-length or least-cost

If many solutions, can find one quickly (quickly moves to depth d)

Simple to implement
Space usually bigger constraint than time, so more usable than BFS for large problems