Design an efficient algorithm that achieves the following task: IN JAVA
 

Given a link list of n floating-point numbers, it returns a two-dimensional link list, say M, of size n × n in which the entry M[i][j] for i ≤ j contains the average of the array entries A[i] through A[j].

That is: if i ≤ j, then M[i][j] = (A[i] + · · · + A[j])/( j − i + 1) , whereas for i > j we have that M[i][j] = 0.

Describe the algorithm that creates this matrix in pseudocode.

What is the running time of your algorithm concerning the link list size n?

Implement the algorithm in Java.

Measure the running time of your Java program for random inputs of size n = 10, 11, 12, etc.  

Does the growth of the running time correspond to your estimates?