SPACE COMPLEXITY

Question

Q:  If b is the branching factor and m is the maximum depth of the search tree, what is the space complexity of greedy search?

I HAVE A DOUBT THAT IIN SOLUTION THE SPACE COMPLEXITY OF BINARY TREE OF HEIGHT N IS GIVEN AS O(2ⁿ ) as i know the space complexity is something equal to  number of levels ..... 

Comments

I didn't exactly understand what your doubt is, but as far the answer to the question is concerned I think it should be b^m for the same reason you've mentioned in the question.

Also thinking intuitively, at every level, the algorithm will have 'b' options to choose from. Hence b x b x b x .... x b    m times.. = b^m.

---

WHAT WE NEED TO SEARCH ?? AND WHERE TRAVERSING EACH LEVEL ???

---

What are we searching?
We're looking for an element which may or may not be in the multi-way Search Tree.

How are we doing it?
Starting from the root, we're checking if the root is our element, no? Then look in the next level, since the branching factor is 'b' the algorithm will have to choose 1 child node (out of 'b' child nodes) of the root. Then from the child, in the worst case, algorithm will have 'b' options to choose from.. And hence forth.

I faced difficulty imagining a search tree having more than 3 nodes, but here is some reference: http://faculty.cs.niu.edu/~freedman/340/340notes/340multi.htm

And since we have 'b' option, at every level and the number of levels are 'm', so O(b^m).

---

THEN HOW IT IS SPACE COMPLEXITY IT SHOULD BE TIME COMPLEXITY???