I am trying to figure out the time complexity of a heuristical algorithm used to solve the Travelling Salesman Problem in a more efficient way than by brute force, ($\theta(n!)$ or similar)

  1. The first step is to compute Kruskal's Minimum Spanning Tree, which to my best knowledge is of $\theta(E+V)$, where E is the number of edges of the graph, and V the number of vertices.

  2. Next, the algorithm finds a minimum-length pairwise matching of the odd degree vertices from the result of the MST graph. Min pairwise matching can solved in $\theta (V'logV')$, where $V'$ represents the vertices that are of odd deg.

My question is, what is the overall time complexity of my Heuristical Algorithm, is it the sum of the two time complexities of 1 and 2?

For further reading on the heuristical algo, consult http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.6.html



Any algorithm that first does $A$ of work and then $B$ of work will have done a total of $A+B$ of work. It doesn't matter what the algorithm is, or what $A$ or $B$ are.

You might be getting confused by steps that look complicated and/or by the fact that $A$ and $B$ are expressed in terms of $\Theta$. For this reason and in general, it is a good idea to try to compute $A+B$ as well as possible, and then finally expressing the sum in terms of Big Oh. Otherwise, you run the risk of performing voodoo, and not really understanding what $\Theta$ means.

| cite | improve this answer | |
  • $\begingroup$ Great, thanks! That is what I was looking for. $\endgroup$ – Aidan Feb 25 '19 at 21:39

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.