# Summation generate by this algorithm

Here is a problem which i'm trying to solve but i can't figure out what is the right answer.

First off the exercise requires us to solve the question for f(n) where n is the size of data used in the function. I am required to do the summation of all +, - ,* or / of line 4,6,7 of the algorithm.

The call to function a(i,j) should not be taken accounted for anything.

Here is the algorithm:

j=3;
for i=1 to n²-1:
while j < i+1 :
a(i,j)= a(i+j, i-j) + 1
for k=1 to j-1 :
a(i,j)=a(i,j)+k(k+1)/2
j=j+1


My current findings were $$\sum_{i=3}^{n²-1}\sum_{j=3}^{i+1} 3 + \sum_{i=3}^{n²-1}\sum_{j=3}^{i+1}\sum_{k=1}^{j-1}3 + \sum_{i=3}^{n²-1}\sum_{j=3}^{i+1} 3$$

I know I am missing something but can't figure out what it is.

Here is how i did find those summations:

j start with a value of 3 so the first for will loop from i=1 to three until it enters the while loop since j < i+1 so since we set j=3 at start for loop will loop until i reaches 3.

Then we will enter the while loop while loop

So at line 4 will get $$\sum_{i=3}^{n²-1}\sum_{j=3}^{i+1} 3$$

Since we have 2 sum (+) , 1 minus (-) operations and both the for loop and the while loop will affect the calculation of operations here

On line 5 we will have

$$\sum_{i=3}^{n²-1}\sum_{j=3}^{i+1}\sum_{k=1}^{j-1}3$$

Since the k=1 for loop will require both other loop and we have 2 sum (+) and a divide (/) operations here

And finally on line 7 we will repeat the same summation as the first

$$\sum_{i=3}^{n²-1}\sum_{j=3}^{i+1} 3$$

• Could you add some thoughts on where your current findings cone from? – mdave16 Jul 26 '17 at 0:16
• Personally, counting quickly i get $(n^2-1)^2 -4$ – mdave16 Jul 26 '17 at 0:21
• j is not reset to 3 after the first while loop? – fonfonx Jul 26 '17 at 0:32
• I have edited my findings on the problem – marting Jul 26 '17 at 0:55

The code:

   j=3;
for i=1 to n²-1:
while j < i+1 :
a(i,j)= a(i+j, i-j) + 1    (4)
for k=1 to j-1:
a(i,j)=a(i,j)+k(k+1)/2  (6)
j=j+1                      (7)


What is going on?

For $i=1$, $j=3$ the while condition is $3 < 2$, so nothing happens.
For $i=2$, $j=3$ the while condition is $3 < 3$, again nada.
For $i=3$, $j=3$ the while condition is $3 < 4$, so we enter the block and have $$a(3,3) := a(6, 0) +1 \\ a(3,3) := a(3,3) + \sum_{k=1}^2 \frac{k(k+1)}{2} \\ j := j+1 = 3+1 = 4$$ As $j = 4 >= i+1 = 4$ we leave the while loop with $i=3, j=4$. Next for iteration follows:

For $i=4$, $j=4$ the while condition is $4 < 5$, so $$a(4,4) := a(8, 0) + 1 \\ a(4,4) := a(4,4) + \sum_{k=1}^3 \frac{k(k+1)}{2} \\ j := 5$$ This pattern repeats until for $i=n^2-1$, $j=n^2 -1$ $$a(n^2-1,n^2-1) := a(2n^2-2, 0) + 1 \\ a(n^2-1,n^2-1) := a(n^2-1,n^2-1) + \sum_{k=1}^{n^2-2} \frac{k(k+1)}{2} \\$$ Line 4: $(n^2-3)$ times 2 additions, 1 subtraction
Line 6: $2 + 3 + \dotsb + (n^2-2) = (n^2-2)(n^2-1)/2-1$ times 2 additions, 1 multiplication, 1 division
Line 7: $(n^2-3)$ times 1 addition

In summary we have these number of operations for Lines 4, 6 and 7:

\begin{array}{c|c} + & 3(n^2 - 3) + (n^2-2)(n^2-1) - 2 = n^4 - 9 \\ - & n^2 - 3 \\ * & n^4 - 3n^2 \\ / & n^4 - 3n^2 \end{array}

• Your answer might be right but i would need to do summations for only line 4-6-7 ... i would need to figure out an answer that would give the required number of operations for line 4 according to previous loop that are affecting line 4 – marting Jul 26 '17 at 0:59
• Line 4 will need $2(n^2 -3)$ additions and $n^2 -3$ subtractions. – mvw Jul 26 '17 at 10:08