2

How many multiplications are performed when the following code fragment is executed? Express your answers in terms of $n$, where $n \geq 10$.

for(i = 1; i < n; i = i + 2)
  for(j= 0; j <= i; j++)
    a[i][j] = a[i][j]*0.001;

Would anyone be able to help me solve it with steps included? I did some other examples and solved them using a double summation, but my algebra skills are lacking when variables are introduced in the inner loop.

Xian
  • 89

1 Answers1

0

The first loop is over all odd integers less than $n$. The second loop is over all integers from $0$ to $i$. There is one multiplication in the inner loop. This gives us that the total number of multiplications is $$2 + 4 + 6 + \ldots + 2\left\lfloor\frac{n}{2}\right\rfloor = 2\left(1+2+\ldots+\left\lfloor\frac{n}{2}\right\rfloor\right) = \left\lfloor\frac{n}{2}\right\rfloor\left(\left\lfloor\frac{n}{2}\right\rfloor+1\right)$$

Explanation: $2$ multiplications for $i=1$ $(j=0,1$), $4$ multiplications for $i=3$ $(j=0,1,2,3)$, and so on up to $n$. Above I have used the formula for the sum of the first $n$ integers.

Kibble
  • 1,157
  • Where did you use the summation formula? The formula does work but I'm lost when trying to solve it using sigma notation. – Xian Oct 06 '15 at 01:36
  • @Xian I used the summation formula to go from $1+2+3+\ldots+n/2$ to $n/2(n/2+1)$. What do you mean by 'using sigma notation'? – Kibble Oct 06 '15 at 01:50
  • Sorry for asking alot later: Where did the the /2 go in the summation formula? The way we were taught it is (n)(n+1)/2, I'm guessing you're replacing n with the floor of n/2, but where does the /2 go in your final answer? I appreciate the help also – Xian Oct 07 '15 at 21:36
  • @Xian I used $2(1+2+\ldots + n) = 2 \cdot \frac{n(n+1)}{2} = n(n+1)$. The $1/2$ gets cancelled by the factor of $2$ in front. – Kibble Oct 09 '15 at 01:19
  • \sum_{i=1}^{\left \lfloor{n/2}\right \rfloor 2i is what I was looking for, since the inner loop produces 2 + 4 + 6 + 8, etc. 2i can then be substituted for the summation formula, which makes 2 * ([n/2] + [n/2]+1)/2 – Xian Oct 11 '15 at 04:33