# Why do depth-limited search algorithm and BFS have different memory complexity?

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)$)?

• Any thoughts? How does BFS work? How much memory does it use when it is visiting a node at depth $i$? – megas Sep 27 '16 at 0:12
• 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. – Raphael Sep 27 '16 at 7:31
• 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? – 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

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})$$.
DFS requires storage of only $$O(bl)$$ nodes thus space complexity is $$O(bl)$$.