Running time of a double loop:

Let A be a two-dimensional array with n rows and n columns and X be a vector of n numbers.

The product of A and X, denoted by AX, is defined as the vector Y with n numbers computed as follows:

Y[i] = A[i][1] + A[i][2] + + A[i][n], for i = 1, 2,, n.

The following algorithm computes AX = Y.

MatVec(A, X)

//input: a two-dimensional array A with n rows and n columns

// and a vector X with n number.

//Output Y = A*X: the matrix-vector product.

1. n = A.rows()

2. for i = 1 to n do

3. Y[i] = 0

4. for j = 1 to n do

5. Y[i] = Y[i] + A[i][j] * X[j]

6. return Y

(a) Express the running time of MatVec as an explicit summation involving i, j, n, and the appropriate constant factors.

(b) Find an explicit formula for your expression in part (a).

(c) Express your answer in part (b) using -notation.