(related to Algorithm: Get the Component Induced by Vertices Connected to a Given Vertex)
Let \(G(V,E)\) be a directed or undirected graph and let \(v\in V\) be one of its vertices. We want to prove that the time complexity of the algorithm \(\mathtt{getCOMPONENT(G,v,m)}\) is \(\mathcal O (|V|+|E|)\).
The time complexity of the first for-next loop in the lines from \(1\) to \(4\) is \(|V|\).
Since the input graph \(G\) is in adjacency list representation and according to the handshaking lemma for undirected graphs, the while loop in the lines from \(5\) to \(14\) is repeated for at most \(2 \cdot |E|\) times, with a constant time complexity of each repetition.
The final for-next loop in the lines from \(15\) to \(20\) has the time complexity of at most \(|V| + |E|\).
Altogether, the time complexity of the algorithm is
\[|V|+2\cdot |E|+ |V|+|E|=\mathcal O(|V|+|E|).\]
