title: Time and Space Complexity for Breadth First Search
body: <p>I just wanted to check if my understanding of the algorithm and calculations given in Russell and Norvig are correct or not.</p>
  
  <p>I am using Missionaries and Cannibals as a problem to test the time and space complexity. Calculating depth is not that big of a deal. I always find the solution at depth 11. What I can't wrap my head around is the branching factor.</p>
  
  <p>Russell and Norvig page 82 says:</p>
  
  <blockquote>
    <p>"There will be <code>O(b^(d-1))</code> nodes in the explored set and <code>O(b^d)</code> nodes
    in the frontier..."</p>
  </blockquote>
  
  <p>My program shows <code>8502</code> nodes in the explored set and <code>14006</code> nodes in the frontier.</p>
  
  <p>Here's the way my thought process is going: If I take the number of nodes and take the <code>d</code> root according to Russell and Norvig, I should get what the branching factor is. Now I have no idea if what I am thinking is correct or not. I just came up with it.</p>
  
  <p>So I take the 10th (d-1) root of <code>8502</code> and get <code>2.47</code> (approximately) and I take the 11th (d) root of <code>14006</code> and get <code>2.39</code> (approximately). So my conclusion is that the branching factor b is roughly <code>2.43</code>.</p>
  
  <p>Am I at all hitting the mark or do I have it completely wrong? This is one of those things that I'm just winging right now. But would love to know if I am wrong or right.</p>