Algorithm 4.1. PrefixAverages1(X)

Input: X- a 1-D numerical array of size n

1) Let A = an empty 1-D numerical array of size n

2) For i = 0 to n-1

3) Let s = X[0]

4) For j = 1 to i

5) Let s = s + X[j]

6) End For

7) Let A[i] = s /(i+1)

End For

Output: An n-element array A of numbers such that A[i]

is the average of elements X[0],X[1], ... ,X[i]

Algorithm 4.2. PrefixAverages2(X)

Input: X- a 1-D numerical array of size n

1) Let A = an empty 1-D numerical array of size n

2) Let s = 0

3) For i = 0 to n-1

4) Let s = s + X[i]

5) Let A[i] = s / (i+1)

6) End For

Output: An n-element array A of numbers such that A[i]

is the average of elements X[0],X[1], ... ,X[i]

1: Computational Complexity

1) What is the difference between the two algorithms? Read these two algorithms carefully. If necessary, it might be helpful to set up an array yourself and apply these two algorithms on it by running through them by hand for small size values of n.

2) Analyse both algorithms by counting primitive operations and derive T(n) for both algorithms. What is the time complexity (Big-Oh, O(n)) of each algorithm? Which one is the most efficient?

2: Implementation

Implement the two algorithms in Java and perform a thorough experimental analysis of their running times. Plot their running times as a function of their input size as scatter plots. Choose representative values of the size n, and run at least 5 tests for each size value n in your tests

Thank you all in advance]]>