63 views

Which of the following search method takes less memory ?

1.  Depth-first search
3.  Linear search
4.  None of the above
in Others
edited | 63 views

DFS or Depth-First Search takes less memory than BFS and Linear Search.

BFS uses a queue, which contains nodes at the front of the search. So at most all nodes at distance d.

whereas, DFS uses a stack, which contains nodes from root to the node being searched. So at most the radius of the graph.

If we consider a balanced k-ary tree and the depth of the tree is $O(log(n))$ and at the lowest level there are $O(n)$ nodes , then

DFS uses $O(log(n))$ memory while BFS uses $O(n)$ memory.

by Boss (15.2k points)
edited

+1 vote