$1.)$ Fill in the space and time complexities $($in terms of the following variables$)$ and indicate if an

algorithm is complete and$/$optimal for each of the algorithms listed in the chart.

b $=$ branching factor

m $=$ maximum depth of tree

g $=$ depth of goal solution

BFS DFS Iterative Deepening UCS A$*$

Time

Space

Optimal?

Complete?

$2.)$ For question $1$ above, explain the rational for the time and space complexities for both BFS

and DFS in your own terms $($essentially$,$ I want to make sure you really understand these

concepts$)$:

a$)$ BFS Time:

b$)$ BFS Space:

c$)$ DFS Time:

d$)$ DFS Space