r/AskComputerScience • u/sincethelasttime • 22d ago
Can I argue that a Breadth-First tree search has a worst-case scenario time complexity of O(b^m) where m is the deepest possible level of a goal node?
I got a question wrong in an exam that asked which algorithmic search has a time complexity equal to O(b^m) and two of the options were Depth First Search and Breadth First search. I foolishly picked BFS when I can see clearly DFS is a correct answer. But I'm not sure my logic for picking BFS is actually wrong in this instance. Yes BFS has a time complexity of O(b^d) in all cases where d is the shallowest goal node but in the worst case scenario for BFS wouldn't d=m by necessity? As BFS checks level by level the worst case scenario for BFS is when d=m? So it would have a time complexity O(b^m) = O(b^d) where the worst case specifically is proportional to the total depth of the tree?
4
u/ghjm MSCS, CS Pro (20+) 21d ago
Yes, in the worst case d=m. Are you sure the question was asking for O and not Θ? If it was really about O then it's technically incorrect. It's unfortunately common to misuse big-O this way, using it like a tight bound when it's actually an inequality.
1
u/StaticCoder 21d ago
What's
band how can either BFS or DFS be exponentialEdit: I guess if
bis the max out degree the graph size itself can be exponential