title: Time complexity of TSP
body: <p>Basically I'm not sure how to measure time complexity. </p>
  
  <p>I know that TSP is an NP-hard problem, that means that the time complexity of an algorithm used to solve it is exponential: O(2^n)</p>
  
  <p>What if I divide into sub-problems and solve the subproblems them combine them to form a complete solution? The time complexity is less right? Maybe something like:  </p>
  
  <p>O(n) = 1 if n = 1
  O(n) = a (n/b) + cn</p>
  
  <p>A problem of size n is divided into a subproblems of size n/b, here cn is linear time complexity. </p>
  
  <p>Ref: <a href="http://devernay.free.fr/cours/algo/docs/10%20-%20Time%20Complexity.pdf" rel="nofollow noreferrer">http://devernay.free.fr/cours/algo/docs/10%20-%20Time%20Complexity.pdf</a></p>
  
  <p>So does that mean time complexity is O(n log n) if you have a divide an conquer approach? I feel like there is something wrong with this logic. It cant be possible to reduce exponential time complexity to n log n through a divide and conquer approach. </p>
  
  <p>What is the time complexity of:
  1 - Solving TSP => exponential O(2^n), right?
  2 - First dividing TSP into subproblems, then solving subproblems using the same approach used in 1? Surely less than exponential?</p>
  
  <p>Sorry I'm a little confused, any help is appreciated.</p>