1
$\begingroup$

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 $$

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

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}

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – marting Jul 26 '17 at 0:59
  • $\begingroup$ Line 4 will need $2(n^2 -3)$ additions and $n^2 -3$ subtractions. $\endgroup$ – mvw Jul 26 '17 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.