Big O time complexity for TSP

Question

I'm currently read on this article - https://core.ac.uk/download/pdf/154419746.pdf and confused about how the O(n^2 * 2^n) time complexity of algorithm 1 is computed. Can someone explain it? I originally thought it was the Bellman-Held-Karp algorithm, but it seems to be slightly different from ordinary pseudo code.

Answer 1

The full algorithm is actually O(n^3 * 2^n). The complexity that you gave is the complexity needed to calculate n problems. But we can find out where that complexity comes from by directly looking at the code. The first loop that we have is this:

foreach w in V do
    …
end do

This is done in exactly n steps. We can ignore this since the second loop is way more complex (and if you add two complexities, the one that is more complex wins) There are four nested loops which means that we need to multiply the single complexities. All of them but one are O(n): for i=2,…|V| clearly since we iterate over all elements in V minus one foreach w in S and foreach u in S: both contain enough elements to qualify for O(n) (in the first iteration 1, then 2, then 4, e.t.c.) And then finally we have the for each subset S of V where the size of S is i . This is combinatorics, but there are 2^n elements where this is true.