5 Consider the following algorithm which is to be applied to a list of numbers.
| Step 1 | Let \(N = 0 , T = 0\) and \(S = 0\). |
| Step 2 | | Input the first number in the list and call it \(X\). | | Delete the first number from the list to give a list that has one number fewer than before. |
|
| Step 3 | Increase \(N\) by 1 , increase \(T\) by \(X\) and increase \(S\) by \(X ^ { 2 }\). |
| Step 4 | If there are still numbers in the list then go back to Step 2. Otherwise go to Step 5. |
| Step 5 | | Calculate \(M = ( T\) divided by \(N )\). | | Calculate \(V = ( S\) divided by \(N ) - ( M\) squared \()\). | | Calculate \(D = \sqrt { } V\). |
|
| Step 6 | Output \(M\) and \(D\). |
- Apply the algorithm to this list.
$$\begin{array} { l l l l l }
3 & 6 & 5 & 7 & 3
\end{array}$$
Record in a table the values of \(X , N , T\) and \(S\) at each pass through Step 3 and give the output values.
- Write down the number of additions and the number of multiplications that are done in Step 3 for a list of five numbers. Hence find the total number of arithmetic operations (additions, multiplications, divisions, subtractions and square roots) that are done in Step 3 and Step 5 when applying the algorithm to a list of five numbers.
- Find an expression for the total number of arithmetic operations that are done in applying the algorithm to a list of \(n\) numbers.
- The total number of arithmetic operations can be used as a measure of the run-time for the algorithm. If it takes approximately 2 seconds to apply the algorithm to a list of 1000 numbers, approximately how long will it take to apply the algorithm to a list of 5000 numbers?