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

enter image description here

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.

As for how many steps does this take when implemented on a Turing machine, this depends on the implementation. Outside of introductory courses on theory of computation, we almost never consider Turing machines, preferring instead to work with more intuitive models such as the RAM machine. Therefore mastering the intricacies of Turing machine behavior is not so important.

  • $\begingroup$ what about my last question? $\endgroup$ – Intuition May 4 '18 at 14:15
  • $\begingroup$ Also your answer said that the above given answer is inaccurate, right? $\endgroup$ – Intuition May 4 '18 at 14:16
  • $\begingroup$ what is "RAM machine"? what do you mean by "the inner part" in the second paragraph? $\endgroup$ – Intuition May 4 '18 at 14:40
  • $\begingroup$ You can find more information on the RAM machine on Wikipedia or using a search engine. $\endgroup$ – Yuval Filmus May 4 '18 at 15:06
  • 2
    $\begingroup$ The answer above seems to mix the Turing machine model with the RAM model. From the point of view of polynomial time, it doesn't matter which model you use, since you can convert a polynomial time algorithm in one machine to a polynomial time algorithm in the other. $\endgroup$ – Yuval Filmus May 4 '18 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.