4 An algorithm is represented by the flow diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-04_1871_1719_293_173} The algorithm is applied with \(n = 4\) and the table of inputs \(\mathrm { d } ( i , j )\) : $$j = 1 \quad j = 2 \quad j = 3 \quad j = 4$$ $$\begin{aligned} & i = 1
& i = 2
& i = 3
& i = 4 \end{aligned}$$ An incomplete trace through the algorithm is shown below. The next box to be used is the box 'Let \(i = t\) '.

1. Complete the trace in the Printed Answer Booklet. The table of inputs represents a weighted matrix for a network, where the weights represent distances.
2. 1. State how the output of the algorithm relates to the network represented by the matrix.
   2. How can the list A be used in the solution of the travelling salesperson problem on the network represented by the matrix?
   3. Write down a limitation on the distances \(\mathrm { d } ( i , j )\) for this algorithm.
3. Explain why the algorithm is finite for any table of inputs. Suppose that, for a problem with \(n\) vertices, the run-time for the algorithm is given by \(\alpha D + \beta T\), where \(\alpha\) and \(\beta\) are constants, \(D\) is the number of times that a value of \(\mathrm { d } ( i , j )\) is looked up and \(T\) is the number of times that \(t\) is updated.
4. Show how this means that the algorithm has \(\mathrm { O } \left( n ^ { 2 } \right)\) complexity. A computer takes 3 seconds to run the algorithm for a problem with \(n = 35\).
5. Use the complexity to calculate an approximate run-time for a problem with \(n = 100\). The run-time using a second algorithm has \(\mathrm { O } ( n ! )\) complexity.
   A computer takes 2.8 seconds to run the second algorithm for a problem with \(n = 35\).
6. Without performing any further calculations, give a reason why the first algorithm is likely to be more efficient than the second for a problem with \(n = 100\).