AI: Uninformed Search Complexities

BFS Time Complexity

O(b^d) where b is the maximum branching factor and d is the depth of the least-cost solution

BFS Space Complexity

O(b^d) as every node is stored

DFS Time Complexity

O(b^m) where b is the maximum branching factor and m is the maximum depth

DFS Space Complexity

O(bm)

Entirely Non-Optimal searches

DFS, Depth-Limited search

Optimal if cost = 1 per step

BFS (not optimal in general), Iterative Deepening Search

Uniform-Cost Search Optimal?

Yes

Bi-directional search optimal?

Yes, if used with the correct strategy, eg. BFS

Entirely complete searches?

IDS, and Bidirectional Search

DFS complete?

No.

Fails in infinite-depth spaces, spaces with loops. 

Can modify to avoid repeated states along path = complete in finite space

Depth-limited search complete?

Not necessarily, the goal must be within depth ‘l’

Uniform-cost search complete?

Yes if step cost >= ∊

• ∊ (epsilon) typically refers to the smallest positive step cost that ensures the algorithm remains optimal.

BFS complete?

Yes (if b is finite)

IDS time complexity

O(b^d), like bfs. D is the depth of the least-cost solution

IDS space complexity

O(bd). similar to DFS O(bm).

• d = depth of least-cost solution

• m = maximum depth of state space

Bidirectional search time and space complexity

O(b^d/2)

Uniform-cost search time and space complexity

# of nodes with g <= cost of optimal solution