Calculating number of steps in multiple loop piece of code

[DrAlexMV]

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]​

Endfor​

Endfor

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 ... "

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

 

[rcgldr]

Shouldn't the first for loop be:

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

 

[DrAlexMV]

It should, but this algorithm comes from the book.

 

[D H]

Shouldn't the first for loop be:

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

Other than a wasted step, it doesn't matter if the upper limit is n or n-1. With an upper lint of n, the inner loop does nothing on that final step when i=n.

 

[DrAlexMV]

So how should I approach this problem? I need to know the T(n) so I can derive the best-case estimate for this algorithm.

 

[rcgldr]

I get conflicting defintions for T(n). Wiki article defines T(n) as O(f(n)):

http://en.wikipedia.org/wiki/Time_complexity

but I also found this:

http://stackoverflow.com/questions/7932424/calculating-tn-time-complexity-of-an-algorithm

You need to find out how T(n) is defined for your class.

 

[DrAlexMV]

The T(n) for the stackoverflow post is the one for this particular exercise. It does not relate to the asymptotic bounds, but to the exact number of steps. With this T(n) you can calculate any asymptotic bound.

 

[rcgldr]

The T(n) for the stackoverflow post is the one for this particular exercise. It does not relate to the asymptotic bounds, but to the exact number of steps. With this T(n) you can calculate any asymptotic bound.

In that case you'd need to write out some example code. Each of these operations counts as a step:

load
store
index
increment
decrement
any math operation

In some cases, it's not clear what counts as a step, considering the differences in processors at the machine language level. How many steps is "i += 4", on a processor like X86 that has an add immediate to memory instruction? How many steps is a scaled index on a processor that can shift an index by 1, 2, 4, or 8 bits when used with an operand of size 8, 16, 32, or 64 bits? What about pre / post decrement or increment on processors that support those addressing modes (ARM, 68000 series, ... ).

 

[DrAlexMV]

This is much more abstract than that.

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]​

Endfor​

Endfor

For example, the outer loop:

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

Runs n times

The second loop:

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

Runs n - 1 times in the first outer loop iteration (when i = 1), then it runs n - 2 times (when i = 2)

So if we just look at the first two loops, and we assume that array addition is a constant operation that only takes 1 step, then the number of steps looks something like this for the first iteration of the outer loop:

n + 1​

Where the + 1 comes from the array addition and storing the result

The overall pattern looks like:

n + 1, n, n - 1, n - 2, ...

All of that happens n times (according to the outer loop)

That looks a lot like the Gaussian summation (not quite because of the + 1 in every term).

The problem is that I do not know how to account for the non-constant array summation in that equation.

 

[rcgldr]

assume that array addition is a constant operation that only takes 1 step.

That would be different than the example shown at stack overflow. In that example, sum = sum + A takes 5 steps: 1 - load index i, 2 - load A, 3 - load sum, 4 - add sum + A, 5 - store back into sum.

Also in the final first loop, where i = n, the second loop does nothing, since j = i + 1 would be j = n+1, so it would loop zero times. This is why I mentioned the first loop should range from 1 to n-1.

 

[rcgldr]

Add up array entries A through A[j].

I forgot to include this in my last post. This would be a third nested loop:

for k = i, i+1, i+2, ... j
... sum += A[k]

The formula for the number of times the inner loop is called will be a cubic equation, a n^3 + b n^2 + c n + d, where "d" is usually zero. You can solve for the coefficients using linear math by generating equations for 4 values of n, such as n = 1, n = 2, n = 3, n = 4. You could write a program to generate counts for the 4 values of n, then solve for the coefficients of the cubic equation.

 

[rcgldr]

I forgot to include this in my last post. This would be a third nested loop:
for k = i, i+1, i+2, ... j
... sum += A[k]
The formula for the number of times the inner loop is called will be a cubic equation, a n^3 + b n^2 + c n + d, where "d" is usually zero.

Since the op stopped responding to this thread, I'll post the formula in order to archive it:

Spoiler

1/6 n^3 + 3/6 n^2 - 4/6 n