• Support PF! Buy your school textbooks, materials and every day products Here!

Calculating number of steps in multiple loop piece of code

  • Thread starter DrAlexMV
  • Start date
  • #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]

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
 
Last edited:

Answers and Replies

  • #2
rcgldr
Homework Helper
8,680
514
Shouldn't the first for loop be:

For i = 1, 2, ..., n-1 ?
 
  • #3
25
0
It should, but this algorithm comes from the book.
 
  • #4
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
683
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.
 
  • #5
25
0
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.
 
  • #7
25
0
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.
 
  • #8
rcgldr
Homework Helper
8,680
514
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, ... ).
 
  • #9
25
0
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.
 
Last edited:
  • #10
rcgldr
Homework Helper
8,680
514
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.
 
  • #11
rcgldr
Homework Helper
8,680
514
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.
 
Last edited:
  • #12
rcgldr
Homework Helper
8,680
514
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:

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

Related Threads on Calculating number of steps in multiple loop piece of code

Replies
10
Views
10K
  • Last Post
Replies
6
Views
2K
Replies
3
Views
4K
Replies
1
Views
14K
Replies
0
Views
3K
Replies
3
Views
1K
Replies
8
Views
655
  • Last Post
Replies
20
Views
1K
Replies
4
Views
559
Top