1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Calculating number of steps in multiple loop piece of code

  1. Sep 6, 2013 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant equations




    3. 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: Sep 6, 2013
  2. jcsd
  3. Sep 6, 2013 #2

    rcgldr

    User Avatar
    Homework Helper

    Shouldn't the first for loop be:

    For i = 1, 2, ..., n-1 ?
     
  4. Sep 7, 2013 #3
    It should, but this algorithm comes from the book.
     
  5. Sep 7, 2013 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  6. Sep 8, 2013 #5
    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. Sep 8, 2013 #6

    rcgldr

    User Avatar
    Homework Helper

  8. Sep 8, 2013 #7
    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.
     
  9. Sep 8, 2013 #8

    rcgldr

    User Avatar
    Homework Helper

    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, ... ).
     
  10. Sep 9, 2013 #9
    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: Sep 9, 2013
  11. Sep 9, 2013 #10

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  12. Sep 9, 2013 #11

    rcgldr

    User Avatar
    Homework Helper

    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: Sep 9, 2013
  13. Sep 11, 2013 #12

    rcgldr

    User Avatar
    Homework Helper

    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Calculating number of steps in multiple loop piece of code
Loading...