Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

Breadth-First Search: Complexity

  • Time complexity is the same magnitude as DFS
    • O (b m )
    • where m is the depth of the solution
  • Space Complexity
    • how many nodes can be in the queue (worst-case)?
    • assume (worst case) that there is 1 goal leaf at the RHS
    • so BFS will store all nodes

      =1 + b + b 2 + ......... + b m
      = O (b m )

Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.