Cost and performance Which is better, depth-first or breadth-first? Worst Worst Shortest Guaranteed to Path? find path? Breadth- first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Sian willams, Spring o3 Worst Case Time for Depth-first Worst case time T is proportional to number of nodes visited Level 0 Level 2 ○○(db*b Sado doodad williams, Spring a33 Brian Williams, Spring 03 10 Cost and Performance Breadth-first Depth-first Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Which is better, depth-first or breadth-first? Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D A B C G C G D C G C S B G A D Brian Williams, Spring 03 11 Worst Case Time for Depth-first Worst case time T is proportional to number of nodes visited Tdfs = bm + … b + 1 Level 1 Level 2 Level 0 b*1 b*b b*bm-1 . . . Level m 1