Chapter 4, Problem 60P

Explanation of Solution

Experimental analysis for prefixAverage1:

With the reference to the textbook, the prefixAverage1 algorithm computes the prefix averages in quadratic time $O\left(n^2\right)$. Now let us take the given algorithm from the textbook for analysis to draw the visualization representation as follows:

Algorithm: prefixAverage1(X,n)

Input: array x on n integers

Output: Array A of prefix averages of X

//Line1

A<- new array of n integers

//Line2

for i<-0 to n-1 do

  //Line3

  S<-X[0]

  //Line4

  for j<-1 to i do

  //Line5

  S<-S+X[j]

  // Line6

  A[i]<-s/(i+1)

//Line7

return A

Explanation:

In the above algorithm,

• The Line1 is to initialize the array of “n” integers and it takes $O\left(n\right)$ time.
• Next the Line2 is the outer for loop which act as counter and executed “n” number of times and it takes $O\left(n\right)$ times to complete the loop.
• The Line3 is assigning the initial element of array to variable “s” and this executes in $O\left(n\right)$ time.
• Line4 is the inner body of for loop executes based on the outer for loop and it follows sum up operation such as 1+2+3+…(n-1). So, this line executes in $O\left(n^2\right)$ time.
• Similar to Line4 and Line 5 follows same running time $O\left(n^2\right)$ because it performs sum up operation inside the for loop.
• On Line6, it calculates the averages for the sum of elements and this is executed in $O\left(n\right)$ time because the operation is directly proportional.
• On Line7, the value is returned and it is executed in constant time O(1).

Visualization representation of algorithm prefixAverage1 in log-log graph:

As the running time of prefixAverage1 is $O\left(1+2+\dots +n\right)$ and the sum of first “n” integers is $\frac{\text{n}\left(\text{n+1}\right)}{\text{2}}$