◀ ▲ ▶Branches / Graph-theory / Proof

Proof

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

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