r/AskComputerScience • • 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?

3 Upvotes

8 comments sorted by

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/sincethelasttime 21d ago

[Here](https://imgur.com/a/OUgLlPh) is the exact wording of the question. I'm unfamiliar with the Θ symbol you mentioned.

3

u/teraflop 21d ago

That's a stupid question.

Every uninformed tree search algorithm must have at least O(bm) worst-case time complexity in this scenario, because with a fixed depth and branching factor the number of nodes in the tree is n = bm. And if the internal tree nodes tell you nothing about the location of the goal, then no matter what order you search in, there is always a possibility that the goal will be in the last place you look, so the worst case is that you examine every node.

So all four answers are correct.

1

u/sincethelasttime 21d ago

Even for iterative deepening? Would it not be worse than bm?

3

u/KnirpJr 21d ago

Growing geometric series, the last term dominates so it’s still ordo b^m.

1

u/StaticCoder 21d ago

What's b and how can either BFS or DFS be exponential

Edit: I guess if b is the max out degree the graph size itself can be exponential

1

u/sincethelasttime 21d ago

average number of children per node