1. Not finding help here? Sign up for a free 30min 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!

Complexity of nested for-loops

  1. Oct 6, 2009 #1
    1. The problem statement, all variables and given/known data
    Find the statement count (not the worst-case scenario) of the following for-loop.

    Code (Text):
    for (int k = 0; k < N; k += 1) {
            for (int m = 0; m < k; m += 1) {
                sum = sum + values[k][m];
            }
            for (int p = k; p < N; p += 1) {
                sum = sum + values[k][m];
            }
        }
     
    3. The attempt at a solution

    For the outer loop:
    k < N and k += 1 are both executed N-times => +2N
    int k=0 and k<N are both executed once more at the beginning => +2
    both inner loops are executed N times => +n(inner-loop-count)

    For the first inner loop:
    Similar to the outer loop, except that it has no inner loop and everything is multiplied by N because of the outer loop => n(2N + N + 2) => 3N^2 + 2n

    For the second outer loop:
    It is executed one time less for each time N increases, but I cannot figure out a formula for it.
    For N=1 -> 3n+2 =5
    for N=2 -> 3n+2 +3(n-1) + 2 = 13
    for N=3 -> 3n+2 +3(n-1) + 2 + 3(n-2) + 2 = 24
    ...

    But what is the general formula?
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?



Similar Discussions: Complexity of nested for-loops
Loading...