## Typo in AI:MA Ch3 pg81

Expand Messages
• The table giving the time and space complexity is wrong for uniform cost search. Instead of b^d it should be b^m for both space and time complexity. This
Message 1 of 1 , Aug 16 9:58 AM
The table giving the time and space complexity is wrong for uniform cost search.  Instead of b^d it should be b^m for both space and time complexity.  This also holds for A* search, so the complexity figures on pg 102 are also in error.

Let me explain.  Let's assume we have a tree where the true solution is 1 layer deep but it requires a cost of 100 to go there.  All other transitions in the tree only cost 1.  (These are all on the non-optimal path).  UCS or A* will expand all of the nodes on the non-optimal paths until depth 100.  The complexity would be b^100 (b^m) for this example.  That is clearly much larger that b^1 (b^d).

I found this while taking a test in my AI class at Brigham Young University.  I had to argue with the teacher to get my points back.

Robert Vogler

Your message has been successfully submitted and would be delivered to recipients shortly.