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

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .