- 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