Answers.Body: <p>The table's &quot;Nodes&quot; column uses rough approximations, as do most of the values in the table, because it is trying to give an intuition about scaling, and not accurate predictive values for any real-world code.</p>
  <p>The true count of nodes value used for the calculations before approximation is based on a branching tree model with branching factor 10, and a variable search depth.</p>
  <p>So the true number of nodes in each case for depth <span class="math-container">$d$</span> and branching factor <span class="math-container">$b$</span> is <span class="math-container">$\sum_{i=1}^d b^i$</span> - summing the number of nodes at each depth of the tree. For <span class="math-container">$b=10, d=6$</span> that is <span class="math-container">$1111110$</span> nodes (decimal).</p>
  <p>If the table was updated to have another digit, then the author would need to write e.g. <span class="math-container">$1.1 \times 10^6$</span> in the nodes column for depth of <span class="math-container">$6$</span>. I guess they felt they had made their point about the scaling that was going on from the pattern in the rows for depths of <span class="math-container">$2$</span> and <span class="math-container">$4$</span>, and wanted to be concise.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-11-12T13:54:56.083Z
Answers.LastActivityDate: 2023-11-12T14:05:30.970Z
Answers.LastEditDate: 2023-11-12T14:05:30.970Z
Answers.UserDisplayName: Neil Slater
Body: <p>I'm currently studying the functionality of BFS and the AIMA book shows</p>
  <p><a href="https://i.sstatic.net/z6sww.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/z6sww.png" alt="these examples of time and memory requirements" /></a>.</p>
  <p>I am unable to replicate them using some trivial calculations.</p>
  <p>For example, if the BFS generates <span class="math-container">$10^6$</span> nodes per second and I have <span class="math-container">$10^6$</span> nodes, it would be obvious that it would take 1 second, not 1,1.</p>
  <p>Please enlighten me, because I don't know if I have to take a different approach.</p>
  
Tags: <norvig-russell><time-complexity><breadth-first-search><space-complexity>
Title: Unable to understand Figure 3.13 Artificial Intelligence: a Modern Approach
UserDisplayName: GABRIEL ÁNGEL CANALS SALLERAS
ThreadText: # Unable to understand Figure 3.13 Artificial Intelligence: a Modern Approach
  
  (Asked by: username_0 on 2023-10-23)
  
  I'm currently studying the functionality of BFS and the AIMA book shows
  
  [![these examples of time and memory requirements](https://i.sstatic.net/z6sww.png)](https://i.sstatic.net/z6sww.png).
  
  I am unable to replicate them using some trivial calculations.
  
  For example, if the BFS generates $10^6$ nodes per second and I have $10^6$ nodes, it would be obvious that it would take 1 second, not 1,1.
  
  Please enlighten me, because I don't know if I have to take a different approach.
  
  **Tags:** norvig-russell, time-complexity, breadth-first-search, space-complexity
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-11-12. Score: 1
  
  The table's "Nodes" column uses rough approximations, as do most of the values in the table, because it is trying to give an intuition about scaling, and not accurate predictive values for any real-world code.
  
  The true count of nodes value used for the calculations before approximation is based on a branching tree model with branching factor 10, and a variable search depth.
  
  So the true number of nodes in each case for depth $d$ and branching factor $b$ is $\sum\_{i=1}^d b^i$ - summing the number of nodes at each depth of the tree. For $b=10, d=6$ that is $1111110$ nodes (decimal).
  
  If the table was updated to have another digit, then the author would need to write e.g. $1.1 \times 10^6$ in the nodes column for depth of $6$. I guess they felt they had made their point about the scaling that was going on from the pattern in the rows for depths of $2$ and $4$, and wanted to be concise.
  
  
  ---
  
  