I'm currently studying the functionality of BFS and the AIMA book shows

these examples of time and memory requirements.

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.


1 Answer 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .