# Proof

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|).$

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition