The following algorithm takes as input a list h1 h2 hn of n

The following algorithm takes as input a list h₁, h₂, ..., h_n of n homework scores, where n 2. Each homework score is a real number from 0 to 100.The algorithm computes the average of the homework scores, where the lowest score is dropped (not included in the calculation.)

procedure HWAvg(h₁, h₂, ..., h_n: a list of n 2 homework scores between 0 and 100)
1. m := 1
2. for i := 2 to n
3. if h_i < h_m then m := i
4. total := 0
5. for j := 1 to n
6. if j m then total := total + h_j
7. return total / (n-1)

a) What is the worst-case runtime of the HWAvg algorithm in notation? Justify your answer by referring to the pseudocode.

b) Give pseudocode for a different algorithm, SimplerHWAvg, that uses only one loop to solve the same problem, and analyze its worst-case runtime in notation. What effect does using only one loop have on the algorithm\'s efficiency?

Solution

Answer to bit-a

There are two loops in above pseudo code.

The loop in line number 2-3 finds the index of the lowest score i,e hm .in the entire list.So to find it, all scores of the array is traversed, So it takes (n) times

Again the loop in line 5-6 sums all scores except lowest. But it has to traverse all scores .which also takes (n) times.

So The pseudo code runs in (n)+ (n) = (n) times

Answer to bit-b

Modified pseudo code (by using one loop)

procedure SimplerHWAvg(h1, h2, ..., hn: a list of n 2 homework scores between 0 and 100)

1. m := 1

2. total=0

3. for i := 2 to n

4.      total=total+hi

5.      if hi < hm then m := i

6. total=total-hm             // lowest score is subtracted from total score

7. return total / (n-1)

Analysis:

In this pseudo code , one loop is used to compute index of lowest score and total score. .This requires traversal of all scores in the list. So it takes So the pseudo code runs in (n) times,

Effects: as per the running time both algorithm have same asymptotic growth.

But considering the actual number steps, modified pseudo code is efficient , as it takes less number of steps(small difference) than that of given pseudo code