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?

  • 3
    $\begingroup$ It would help if you explained the 2-opt method and what problem it is supposed to solve. $\endgroup$ Mar 21, 2013 at 1:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.