Determining the exact number of executions of an algorithm

Question

I have algorithm such as:

for(int i=1; i<=n; i++)
  for(int j=1; j<=2*n; j=j+2)
     for(int k=i; k<=j; k++)
        instr;

I need to find a formula that will determine how many times the "instr" instruction will be executed.

I wrote this. . But I'm getting incorect values. For example for n=4, the "instr" will be executed 43 times but I'm getting 40 from my sum.

Where I messed up?

Answer 1

From the code

int count = 0;
for(int i=1; i<=n; i++)
  for(int j=1; j<=2*n; j=j+2)
     for(int k=i; k<=j; k++)
         count++;

one can transform it in the semantically equivalent:

int count = 0;
for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++)
        for(int k=i; k<=2*j - 1; k++)
           count++;

If one would print the count variable at the end of both code versions its values would be:

       |  loop 1 | loop 2
________________________________ 
N = 1  |    1    |   1
N = 2  |    6    |   6
N = 3  |    19   |   19 
N = 4  |    43   |   43 
N = 5  |    82   |   82

From the second loop you extracted the formula:

Which makes sense in paper, however, there is a there is a catch. Converting your formula into code:

   public static int third_loop(int n ){
        int count = 0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                count += (2 * j - 1)  - i + 1;
        return count;
    }

and showing the values of the variable count:

       | loop  1 | loop 2 | loop 3
____________________________________
N = 1  |    1    |   1    |    1
N = 2  |    6    |   6    |    6
N = 3  |    19   |   19   |    18
N = 4  |    43   |   43   |    40 
N = 5  |    82   |   82   |    75

The count values are now different, and the reason for this is that there will be iterations where (2 * j - 1) < i + 1, hence the formula (2 * j - 1) - i + 1 will produce negative results, and add those results to the variable count. Something that was implicitly avoided on the second loop. If one would change the third loop to:

  public static int fourth_loop(int n ){
        int count = 0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                count += Math.max((2 * j - 1)  - i + 1, 0);
        return count;
    }

one would get:

      | loop  1 | loop 2  | loop 3  | loop 4
__________________________________________
N = 1  |    1    |   1    |    1    |  1
N = 2  |    6    |   6    |    6    |  6
N = 3  |    19   |   19   |    18   |  19
N = 4  |    43   |   43   |    40   |  43
N = 5  |    82   |   82   |    75   |  82

So the problem with your formula is that it is also factoring the negative values whereas your code is not. Since, I do not have the mathematical tools to give you the precise formula I ask your friends from math.stackexchange to do so.

EDIT: From the bounty that I have offered, Matthew Towers came out with the following exact expression: