Time/Space Complexity of Depth First Search

Question

I've looked at various other StackOverflow answer's and they all are different to what my lecturer has written in his slides.

Depth First Search has a time complexity of O(b^m), where b is the maximum branching factor of the search tree and m is the maximum depth of the state space. Terrible if m is much larger than d, but if search tree is "bushy", may be much faster than Breadth First Search.

He goes on to say..

The space complexity is O(bm), i.e. space linear in length of action sequence! Need only store a single path from the root to the leaf node, along with remaining unexpanded sibling nodes for each node on path.

Another answer on StackOverflow states that it is O(n + m).

Answer 1

Time Complexity: If you can access each node in O(1) time, then with branching factor of b and max depth of m, the total number of nodes in this tree would be worst case = 1 + b + b² + … + b^m-1. Using the formula for summing a geometric sequence (or even solving it ourselves) tells that this sums to = (b^m - 1)/(b - 1), resulting in total time to visit each node proportional to b^m. Hence the complexity = O(b^m).

On the other hand, if instead of using the branching factor and max depth you have the number of nodes n, then you can directly say that the complexity will be proportional to n or equal to O(n).

The other answers that you have linked in your question are similarly using different terminologies. The idea is same everywhere. Some solutions have added the edge count too to make the answer more precise, but in general, node count is sufficient to describe the complexity.

---

Space Complexity: The length of longest path = m. For each node, you have to store its siblings so that when you have visited all the children, and you come back to a parent node, you can know which sibling to explore next. For m nodes down the path, you will have to store b nodes extra for each of the m nodes. That’s how you get an O(bm) space complexity.