probably this question was asked before, however, I am not sure how I can calculate the space complexity of DFS. for example in this situation, branching factor(b) is 3 and depth(d) is 5 and each node requires 10 bytes of memory to represent. how can I calculate the space complexity ?
1
votes
Try searching the Internet for "space complexity of depth first search"?
– anatolyg
How is the number of bytes per node related to the space complexity(it does not matter as long as it is a constant)?
– kraskevich
The space complexity is O(d).
– Yves Daoust
as I saw on russel and norvig book space complexity os DFS is b.m(max depth) then I saw this question and I didnot find the solution(actually I don't understand how I can calculate it)
– gulsen
1 Answers
1
votes
It depends over what kind of structure you perform the depth first search (DFS):
- over a tree: you need not check whether you have visited a state before and must only store the current trace (in a stack), which becomes maximally depth $d$. For each state on the trace, you need to store which outgoing transitions you have traversed already, which becomes maximally the maximal branching factor $b$ for each state. Thus you require $O(d * b)$ space.
- over a graph: you need to additionally check whether you have visited a state before by storing all states already visited, e.g. in a hash table. Thus you require $O(d * b + |V|)$ space, with V being the set of vertices. On the interwebs, you usually read that the space complexity is $O(|V|)$; usually the number of states is the major factor, but if your state space has a large $b$, do not ignore this part of the space requirement!
