Runtime of a nested Loop with increment 3

Question

I am trying to analyze run time of the following algorithm

1. int sum = 0;
2. for (int i = 1; i <= n; i++)
3.   for(int j=i; j <= n; j=j+3)
4.      sum++;  

I am trying to write exact run time of the inner loop and come up with this expression: $ c\sum_{i=1}^{n} \frac{n-i}{3}+1 $ where $c$ is a constant for operations. By some manipulation I wrote it like $c\frac{n^2+5n}{6}$. My question is:
For actual number of iterations I need to use floor function for $\frac{n-i}{3}$ but I couldn't manipulate it. How can I do it?

Answer 1

If I understand the question correctly,

the exact number of operations is $$ 1 + \sum_{i=0}^{\lfloor 3/n\rfloor} (n-3i) $$

this can be obtained by observing that since you take the floor operation after diving by 3 in the number of iterations for the inner loop (i.e. the inner loop executes $\lfloor (n-i)/3\rfloor$ iterations), then if you take any three indexes $i$ for the outer loop s.t. the remainder when dividing its predecessor by 3 is the same (e.g. {1,2,3}, {4,5,6}, and so on) the inner loop will execute the same amount of iterations.

Therefore, you can count the operations in the outer loop "in blocks of three".

Hope this helps!