Let be $b$ the branching factor of the tree.

Let be $d$ the depth of the shallowest solution.

Let be $l$ the limit given to depth-limited search algorithm

Why is depth-limited search algorithm memory complexity $\mathcal O(b)$ times something (which is actually $\mathcal O(bl)$) whereas BFS is $\mathcal O(b)$ power something (which is actually $\mathcal O(b^d)$)?

  • 3
    $\begingroup$ Any thoughts? How does BFS work? How much memory does it use when it is visiting a node at depth $i$? $\endgroup$ – megas Sep 27 '16 at 0:12
  • $\begingroup$ What is $B$? Are these bounds supposed to be tight? (I don't think so.) Your title and post disagree (BFS vs DFS); please clarify. $\endgroup$ – Raphael Sep 27 '16 at 7:31
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Sep 27 '16 at 7:31

Let be b the branching factor of the tree.

Let be d the depth of the shallowest solution.

Let be l the limit given to depth-limited search algorithm

Breadth-first search (BFS)

In the worst case, suppose that our solution is at depth d, and we expand all nodes but the last node at level d, then the total number of generated nodes is $ O(b^{d}) $.

As all these nodes must retain in memory while we expand our search, then the space complexity is $O(b^{d})$.

Depth-limited search algorithm

Unlike BFS, Depth-limited search algorithm has a very modest memory requirements, it needs to store only the path from the root to the leaf node, beside the siblings of each node on the path. Depth-limited search algorithm removes a node from memory once all of its descendants have been expanded.

DFS requires storage of only $O(bl)$ nodes thus space complexity is $O(bl)$.

  • $\begingroup$ 1) You argue (less than formally) for a lower bound; you can't prove an upper bound this way. 2) I think you need to add some arguments to your statements. $\endgroup$ – Raphael Sep 27 '16 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.