Statements.
BFS runs in exponential time \(\mathcal{O}(b^{d + 1})\), where
- \(b\) is the branching factor and
- \(d\) is the depth of the shallowest solution.
BFS runs in linear time \(\mathcal{O}(|V| + |E|)\), where
- \(|V|\) is the cardinality of the vertex set and
- \(|E|\) is the cardinality of the edge set.
Objective.
Prove the above statements equivalent for any complete graph \(K_n\).
Proof.
Lemma 1. Given \(|V| = n\), prove \(\mathcal{O}(|V| + |E|) = \mathcal{O}(n^2)\).
For any \(K_n\),
\[\begin{align*}
|V| = n \> \iff \> |E| = \frac{n(n - 1)}{2},
\end{align*}
\]
and so
\[\begin{align*}
\mathcal{O}(|V| + |E|)
& = \mathcal{O}(|V|) + \mathcal(|E|)
&& \text{distribute \(\mathcal{O}\)}
\\[1ex]
& = \mathcal{O}(n) + \mathcal{O} \big( n(n - 1) / 2 \big)
&& \text{substitute \(|V|\) and \(|E|\)}
\\[1ex]
& = \mathcal{O}(n) + \mathcal{O} \big( (n^2 - n) / 2 \big)
&& \text{distribute \(n\)}
\\[1ex]
& = \mathcal{O}(n) + \mathcal{O} \big( (1/2) (n^2 - n) \big)
&& \text{split fraction}
\\[1ex]
& = \mathcal{O}(n) + \mathcal{O} \big( (1 / 2) n^2 - (1 / 2) n \big)
&& \text{distribute \(1/2\)}
\\[1ex]
& = \mathcal{O}(n) +
\mathcal{O}\big((1 / 2) n^2 \big) -
\mathcal{O}\big((1 / 2) n \big)
&& \text{distribute \(\mathcal{O}\)}
\\[1ex]
& =
\mathcal{O}(n) +
\mathcal{O} \big( 1/2 \big) \, \mathcal{O} \big( n^2 \big) -
\mathcal{O} \big( 1/2 \big) \, \mathcal{O} \big (n \big)
&& \text{distribute \(\mathcal{O}\)}
\\[1ex]
& =
\mathcal{O}(n) +
\mathcal{O}(1) \, \mathcal{O}(n^2) -
\mathcal{O}(1) \, \mathcal{O}(n)
&& \text{standardize}
\\[1ex]
& = \mathcal{O}(n^2).
&& \text{simplify}
\end{align*}
\]
Lemma 2. Given \(|V| = n\), prove \(\mathcal{O}(b^{d + 1}) = \mathcal{O}(n^2)\).
In any \(K_n\), all vertices are of degree \(n - 1\) and adjacent, so
\[b = n - 1 \qand d = 1, \]
respectively, which gives
\[\begin{align*}
\mathcal{O}(b^{d + 1})
& = \mathcal{O} \big( (n - 1)^{1 + 1} \big)
&& \text{substitute \(b\) and \(d\)}
\\[1ex]
& = \mathcal{O} \big( (n - 1)^2 \big)
&& \text{combine like terms}
\\[1ex]
& = \mathcal{O} \big( (n - 1)(n - 1) \big)
&& \text{take square}
\\[1ex]
& = \mathcal{O} \big( n^2 - 2n + 1 \big)
&& \text{multiply binomials}
\\[1ex]
& = \mathcal{O}(n^2) - \mathcal{O}(2n) + \mathcal{O}(1)
&& \text{distribute \(\mathcal{O}\)}
\\[1ex]
& = \mathcal{O}(n^2) - \mathcal{O}(n) + \mathcal{O}(1)
&& \text{standardize}
\\[1ex]
& = \mathcal{O}(n^2).
&& \text{simplify}
\end{align*}
\]
Given Lemma 1 and Lemma 2,
\[\begin{align*}
\mathcal{O}(|V| + |E|) & \stackrel{?}{=} \mathcal{O}(b^{d + 1}) \\
\mathcal{O}(n^2) & \stackrel{\checkmark}{=} \mathcal{O}(n^2).
\quad \blacksquare
\end{align*}
\]