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.

Depth-First Search: Complexity

    Time Complexity
      assume (worst case) that there is 1 goal leaf at the RHS
      so DFS will expand all nodes

      =1 + b + b2+ ......... + bm
      = O (b m )
      where m is the max depth of the tree

    Space Complexity
      how many nodes can be in the queue (worst-case)?
      at each depth l < d we have b-1 nodes
      at depth m we have b nodes
      total = (d-1)*(b-1) + b = O(bm)

Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.