🏗️ $\Theta \rho ϵ\eta \Pi \alpha \tau \pi$🚧 (under construction)

Let $X_k$ be the collection of all nodes which have a path of length $k$ connecting them to $s$ and that $X_0=\left\{s\right\}$. We will prove by that BFS will expand every node in $X_k$ by induction.

For the base case we know that $X_0=\left\{s\right\}$ will be expanded on the initial iteration, so the claim holds. Now assume that it holds true for every $k\in {\mathbb{N}}_0$, and we'll show that it holds true for $k+1$.

We know that BFS will expand every node in $X_k$, we also know that any vertex that has depth $k+1$, is a neighbor of a node that had length $k$, therefore by expanding every node in $X_k$, this means that $X_{k+1}$ will be contained on the queue, and therefore will expand every vertex in $X_{k+1}$

Observe that there are at most $b^k$ nodes in $X_k$ (symbolically $\left|X_k\right|\le b^k$), therefore to expand everything in layer $X_k$ it will take at most $b·b^k=b^{k+1}$ steps to expand every vertex in $X_k$ while enqueuing their neighbors. Therefore, since we've proven that BFS expands by depth layer, then we would say that the runtime is upper bounded by

$${\displaystyle b^1+b^2+\dots b^{k+1}}$$

We'll also note that during the last layer, we could find our goal node immediately if it is the first thing we expand at depth $d$. But in the worst case, we iterate through every vertex in $X_{d-1}$, and finally add in the node $g$ at the end of the queue, this means we will have to expand $\left|X_d\right|-1$ vertices before we finally expand $g$, which results in at most $b·\left(\right|X_d|-1)\le b(b^d-1)=b^{d+1}-b^d$ steps taken by BFS, which is why our upper bound involving just $b^{k+1}$ above is justified. Also we can simplify inside the big-o:

$${\displaystyle \mathcal{O}(b^1+b^2+\dots +b^{k+1})=\mathcal{O}\left(b^{k+1}\right)}$$ as needed.

The space taken by BFS is directly given by the amount of space used up by the queue, we can assume that everything in the queue has constant size, but we note that in the worst case as we iterate over vertices in $X_d$, $g$ is the last one to be popped off, therefore the queue would contain $b·\left(\right|X_d|-1)\le b(b^d-1)$ vertices, which is upper bounded by $b^d+1$ vertices, as needed.