1. Perform careful experimental analysis of their running times by doing the following:
2. a. For each algorithm, choose at least 5 appropriate values for n, where n is the input array size, and determine how long it takes to run in microseconds. Please note the following:

• One good strategy is to grow the input size by repeated doubling (e.g 200000,400000,800000, etc).
• If your timings are erratic (e.g. 0s or there is no clear increase in time with respect to input size), try choosing larger values for n.
• You are not required to use the same values of n for both algorithms.

2. Plot the running times obtained in part (a) as a function of n as scatter plots on a linear scale for each algorithm.

Algorithm prefixAveragesi (x): Input: An n-element array X of numbers. Output: An n-element array A of numbers such that A[i] is the average of elements X(O).....X[i]. Let A be an array of numbers. for i = 0 to 1-1 do 40 for jo to i do a +a+X[j] A[i] -- a/(1+1) return array A Algorithm 1.14: Algorithm prefixAverages1. Algorithm prefixAverages2(x): Input: An n-clement array X of numbers. Output: An n-element array A of numbers such that A[ij is the average of elements XO),..., X[1. Let A be an array of n numbers. S+0 for i 0 to 1-1 do 5+5+X[] Ai -- 5/(i+1) return array A Algorithm 1.15: Algorithm prefixAverages2. Algorithm prefixAveragesi (x): Input: An n-element array X of numbers. Output: An n-element array A of numbers such that A[i] is the average of elements X(O).....X[i]. Let A be an array of numbers. for i = 0 to 1-1 do 40 for jo to i do a +a+X[j] A[i] -- a/(1+1) return array A Algorithm 1.14: Algorithm prefixAverages1. Algorithm prefixAverages2(x): Input: An n-clement array X of numbers. Output: An n-element array A of numbers such that A[ij is the average of elements XO),..., X[1. Let A be an array of n numbers. S+0 for i 0 to 1-1 do 5+5+X[] Ai -- 5/(i+1) return array A Algorithm 1.15: Algorithm prefixAverages2