- #1

- 25

- 0

## Homework Statement

The following pseudocode demonstrates an algorithm to create a 2D array from a 1D array by adding elements into certain rows:

For i = 1, 2, ..., n

For j = i + 1, i + 2, ..., n

Add up array entries A

*through A[j]*

Store the result in B[i, j]Store the result in B[i, j]

I am supposed to create a T(n) expression for the number of steps but I am not sure how to go about the second loop which depends on the first one. I am also not sure how to do so for the "Add up array entries ... "

Well, my idea was that since the number of steps on the loops themselves follow the Gaussian summation formula for the outer loops to model it this way:

T(n) = n(n - 1)/2

That does not account for the array summation which is O(n) but I am not sure what its T(n) is

Endfor

EndforI am supposed to create a T(n) expression for the number of steps but I am not sure how to go about the second loop which depends on the first one. I am also not sure how to do so for the "Add up array entries ... "

## Homework Equations

## The Attempt at a Solution

Well, my idea was that since the number of steps on the loops themselves follow the Gaussian summation formula for the outer loops to model it this way:

T(n) = n(n - 1)/2

That does not account for the array summation which is O(n) but I am not sure what its T(n) is

Last edited: