Question:
What is the worst-case space complexity of Depth-First Search (DFS) on a tree of height \(h\) and branching factor \(b\)?
ऊंचाई \(h\) और ब्रांचिंग फैक्टर \(b\) वाले ट्री पर गहराई-पहला खोज (DFS) की सबसे खराब स्थिति की स्थान जटिलता (space complexity) क्या है?
Options:
- \(O(b \cdot h)\) (or \(O(h)\) if only current path is stored)
- \(O(b^h)\)
- \(O(h^2)\)
- \(O(b)\)
- \(O(b \cdot h)\) (या केवल वर्तमान पथ के लिए \(O(h)\))
- \(O(b^h)\)
- \(O(h^2)\)
- \(O(b)\)
Correct Answer: a)
Explanation:
DFS requires storing only the current path from the root down to the leaf plus unvisited siblings at each level, which is \(O(b \cdot h)\) (linear in height), unlike BFS which requires \(O(b^h)\) exponential space.
DFS की मेमोरी आवश्यकता ट्री की ऊंचाई के समानुपाती \(O(b \cdot h)\) होती है, जबकि BFS को घातीय \(O(b^h)\) मेमोरी चाहिए।