---
title: "Informed vs blind search; DFS vs BFS"
subject: "Artificial Intelligence"
chapter: 3
key: "semester_6/artificial_intelligence:informed-vs-blind-search-dfs-bfs"
source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/informed-vs-blind-search-dfs-bfs
site: BCT Engineering
---

# Informed vs blind search; DFS vs BFS

Artificial Intelligence · Chapter 3: Search Techniques

- Asked in: 2070 Bhadra, 4+4 marks
- Video: [Lec-5: Uninformed Vs Informed Search in Artificial Intelligence with Example](https://www.youtube.com/watch?v=gZpUcsB9TFc) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/informed-vs-blind-search-dfs-bfs
- Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-3

## Question

Differentiate between informed and blind search. How is depth first search different from breadth first search? Compare with evaluation parameters.

## Short answer

Informed search uses a heuristic h(n) to guide toward the goal; blind search uses only the problem definition. BFS expands level by level with a queue, is complete and optimal for equal costs, with time and space O(b^d). DFS uses a stack, goes deep first, needs O(b*m) space but may fail in infinite spaces.

## Answer

#### Informed vs blind (uninformed) search
| Basis | Blind (uninformed) search | Informed (heuristic) search |
|---|---|---|
| Knowledge used | Only the problem definition | Problem-specific knowledge as a heuristic h(n), the estimated cost to the goal |
| Direction | Systematic, no idea of goal direction | Guided towards the goal |
| Efficiency | Explores many unnecessary nodes; slow | Explores fewer nodes; faster |
| Time and space | Usually very high | Much lower with a good heuristic |
| Optimality | Only some (BFS with equal cost, UCS) | A* with an admissible heuristic is optimal |
| Examples | BFS, DFS, uniform-cost, depth-limited, iterative deepening | Greedy best-first, A*, hill climbing, beam search |

#### DFS vs BFS
- **BFS** expands nodes level by level using a FIFO queue; **DFS** goes as deep as possible along a branch before backtracking, using a LIFO stack (or recursion).
- Example tree A → (B, C), B → (D, E), C → (F, G): BFS visits A B C D E F G; DFS visits A B D E C F G.

With b = branching factor, d = depth of shallowest goal, m = maximum depth:

| Evaluation parameter | BFS | DFS |
|---|---|---|
| Completeness | Complete | Not complete in infinite or cyclic spaces |
| Optimality | Optimal when step costs are equal | Not optimal |
| Time complexity | O(b^d) | O(b^m) |
| Space complexity | O(b^d) (stores all nodes of a level) | O(b·m) (stores one path) |
| Data structure | Queue | Stack |
| Behaviour | Finds the shallowest goal | May find a deep goal first or go into an infinite branch |
| Suitable when | Solution is shallow, shortest path needed | Memory is limited, many solutions deep in the tree |

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the key difference between informed and blind search?
   A. Informed search uses a heuristic h(n) estimating cost to the goal; blind search uses only the problem definition
   B. Blind search always uses a heuristic and informed search never does
   C. Informed search uses a stack; blind search uses a queue
   D. Informed search explores more nodes
   Answer: A. Informed search is guided by problem-specific knowledge h(n), so it usually explores fewer nodes. (Key point: Informed vs blind)

2. Which list contains only informed search methods?
   A. BFS, DFS, uniform-cost
   B. Greedy best-first, A*, beam search
   C. Depth-limited, iterative deepening, BFS
   D. DFS, A*, uniform-cost
   Answer: B. Greedy best-first, A* and beam search use heuristics; BFS, DFS, UCS, DLS and IDS are blind. (Key point: Examples of each)

3. For b = branching factor, d = shallowest goal depth, m = max depth, what are the space complexities of BFS and DFS?
   A. BFS O(b·m), DFS O(b^d)
   B. BFS O(b^d), DFS O(b·m)
   C. Both O(b^m)
   D. BFS O(b·d), DFS O(b^m)
   Answer: B. BFS stores a whole level, O(b^d); DFS stores one path with siblings, O(b·m). (Key point: DFS vs BFS space)

4. Why is DFS not complete in general?
   A. It cannot use a stack
   B. It can go down an infinite branch or loop in a cyclic space and never find the goal
   C. It only visits the root
   D. It stores too few nodes to terminate
   Answer: B. DFS keeps going deeper along a branch, so in an infinite or cyclic space it may never return. (Key point: Completeness)

## Related in Artificial Intelligence

- [Searching: BFS vs DFS comparison](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ablind-search-dfs-bfs-compare) — Artificial Intelligence, chapter 3, asked 5×
- [Informed vs uninformed; min-max; alpha-beta](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ainformed-uninformed-minmax-alphabeta) — Artificial Intelligence, chapter 3
- [Advantage of depth limit search](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Adepth-limit-search-advantage) — Artificial Intelligence, chapter 3

## Related in other subjects

- [Differences between DFS and BFS](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adfs-vs-bfs-differences) — Data Structure and Algorithm, chapter 10
- [BFS and DFS with example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abfs-dfs-explain-example) — Data Structure and Algorithm, chapter 10, asked 4×
- [Breadth first traversal in graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abfs-graph-explain) — Data Structure and Algorithm, chapter 10, asked 2×
- [Rectangular beam dimensions, depth twice breadth](https://www.bctengineer.com/question.md?key=semester_3%2Fstrength_of_materials%3Arect-beam-udl-point-load-depth) — Strength of Materials, chapter 7