The Gateway to Computer Science Excellence
0 votes

Which of the following search method takes less memory ?

  1.  Depth-first search
  2.  Breadth-first search
  3.  Linear search
  4.  None of the above
in Others by Boss (17.5k points)
edited by | 66 views

1 Answer

0 votes

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.4k points)
edited by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,274 answers
104,797 users