Consider the following terminology and match List 1 and List 2 and choose the correct answer from the code given below

b = branch factor

d = depth of shallowest solution

M = Maximum depth of the search tree

I = depth limit

List 1	List 2
a) BFS	i) O(bd)
b) DFS	ii) O(bd)
c) Depth – Limited Search	iii) O(bm)
d) Iterative deepening Search	iv) O(bl)

BFS:

Breadth first search in artificial intelligence is implemented as FIFO. Path is find out by considering the number of edges in that path. Start from the root node, it considers all the nodes. But at the end, selects the path having lowest number of edges. If b is the branching factor and d is the depth. Then overall cost of BFS is O(b^d).

DFS:

It is based on the concept of LIFO as that of stack procedure. It considers the nodes one by one from root node to the leaf as a single path. If it does not terminate it can go to the infinity. If b is the branching factor and m is the depth. Then cost of DFS is O(bm).

Depth – Limited Search

In this, depth is specified first, and all the nodes are traversed till that depth then it goes on to next level. If b is the branching factor. Then overall cost of depth limited search is O(bl).

Iterative – deepening search:

It starts from root node i.e. depth 1, expands all the nodes and then goes on to the depth 2, expand all the nodes of that depth. In this way, it expands all the nodes. If b is the branching factor and d is the depth, then overall cost is O(bd).