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).

Solution 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.

Solution 2

The complexity is O(n + m) where n is the number of nodes in your tree, and m is the number of edges.

The reason why your teacher represents the complexity as O(b ^ m), is probably because he wants to stress the difference between Depth First Search and Breadth First Search.

When using BFS, if your tree has a very large amount of spread compared to it's depth, and you're expecting results to be found at the leaves, then clearly DFS would make much more sense here as it reaches leaves faster than BFS, even though they both reach the last node in the same amount of time (work).

When a tree is very deep, and non-leaves can give information about deeper nodes, BFS can detect ways to prune the search tree in order to reduce the amount of nodes necessary to find your goal. Clearly, the higher up the tree you discover you can prune a sub tree, the more nodes you can skip. This is harder when you're using DFS, because you're prioritize reaching a leaf over exploring nodes that are closer to the root.

Solution 3

I suppose this DFS time/space complexity is taught on an AI class but not on Algorithm class.

The DFS Search Tree here has slightly different meaning:

A node is a bookkeeping data structure used to represent the search tree. A state corresponds to a configuration of the world. ... Furthermore, two different nodes can contain the same world state if that state is generated via two different search paths.

Quoted from book 'Artificial Intelligence - A Modern Approach'

So the time/space complexity here is focused on you visit nodes and check whether this is the goal state. @displayName already give a very clear explanation.

While O(m+n) is in algorithm class, the focus is the algorithm itself, when we store the graph as adjacency list and how we discover nodes.