CODEWITHSUNDEEP
algorithmartificial-intelligence
gulsen
gulsen

Reputation: 103

space complexity of depth first search

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 ?

Upvotes: 1

Views: 1779

Answers (1)

DaveFar
DaveFar

Reputation: 7457

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!

Upvotes: 1

Related Questions