title: Time/Space Complexity of Depth First Search
body: <p>I've looked at various other StackOverflow answer's and they all are different to what my lecturer has written in his slides.</p>
  
  <blockquote>
    <p>Depth First Search has a time complexity of O(b^m), where b is the
    maximum branching factor of the search tree and m is the maximum depth
    of the state space. Terrible if m is much larger than d, but if search
    tree is "bushy", may be much faster than Breadth First Search.</p>
  </blockquote>
  
  <p>He goes on to say..</p>
  
  <blockquote>
    <p>The space complexity is O(bm), i.e. space linear in length of action
    sequence! Need only store a single path from the root to the leaf
    node, along with remaining unexpanded sibling nodes for each node on
    path.</p>
  </blockquote>
  
  <p><a href="https://stackoverflow.com/questions/10118580/time-complexity">Another answer</a> on StackOverflow states that it is O(n + m).</p>