Design and Analysis of Algorithms

280 Design and Analysis of Algorithms

The path can be found by noting the node which resulted in minimum cost at each stage. What is the

complexity of this algorithm? We can proceed as follows:

The number N of s(i, S) to be computed before the equation 11.1, for s(1, V − {1}) can be used, is

given by:

N = Σ(n − 1)

2−

⎛⎞

⎜⎟

⎝⎠

n

k

for k = 0 to n − 2, (11.2)

because for each value of |S | there are (n − 1) choices for i and the number of distinct sets of size k, not

considering 1 and i in S, is comb(n − 2, k).

From the equation 11.2, N = (n − 1)2

n − 2

, thus the algorithm will require O(n

2

2

n

), as the computation of

s(i, S) for |S | = k requires (k