Analyzing Iterative Deepening Search

$($a$)$ Time Complexity Prove that if there is a solution at depth d and the branching factor of the

search tree is b then iterative deepening search expands O$($b

d

$)$ nodes

$($b$)$ A Bad Example Give an example with of a graph n nodes where breadth first search and depth

first search both expand O$($n$)$ nodes while iterative deepening search expands O$($n

$2$

$)$ nodes.

$($c$)$ Understanding Time Complexity Explain why your answer to part $($a$)$ is correct given your

example from part $($b$)$

Prove that if there is a solution at depth d and the branching factor of the search tree is b then iterative

deepening search expands O$($b

d

$)$ nodes