I'm doing a practice test for a course on routing problems. There's a question asking to infere the time complexity of the 2-opt method.

I can see that the complexity per iteration is in $O(n^2)$ because you need to check all combinations of 2 arcs. I don't know how to calculate the worst case number of iterations though. The paper we got doesn't say anything about it's tc, so i'm kind of stuck here.

How do i calculate this?

  • 2
    $\begingroup$ It would help if you explained the 2-opt method and what problem it is supposed to solve. $\endgroup$ – Yuval Filmus Mar 21 '13 at 1:30
  • $\begingroup$ "The paper we got". Which paper was it? $\endgroup$ – nbro Nov 12 '18 at 14:49

Your Answer

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

Browse other questions tagged or ask your own question.