# Analysing the algorithm of a language called CONNECTED in Sipser to show that it belongs to class P

The question and its answer is given in the following picture:

But I do not understand why stage 2 causes at most $n+1$ repetitions, and why stage 3 uses at most $O(n^2)$ steps, and I understand that the algorithm runs in $O(n^4)$ time not $O(n^3)$ as written, am I right?

Step 2 causes at most $n$ repetitions since each repetition other than the last one marks a node which wasn't previously marked. Since there are only $n$ nodes and one of them is marked in Step 1, there are at most $n-1$ repetitions which mark a new node, and one more which doesn't (and so moves to Step 4).
In Step 3, we go over all nodes in $G$ ($n$ nodes), and check all its neighbors ($n-1$ neighbors), so there are at most $n(n-1)$ repetitions of the inner part.