Counting Iterations

Question

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 = 0; i < 8; i++)
  for(j= i+1; j < n; j++)
    a[i][j] = a[i][j]*0.001;

With a little trial and error I can see that $8n - 36$ seems to work when $n \geq 10$, but I was curious on how to derive it. I understand that you get a double summation and simplify in terms of $N$, but the inner loop is throwing me off as I've never done double summation with an extra variable.

Answer 1

Work it out from the inside summation.

$\sum_{i=0}^7 \sum_{j=i+1}^{n-1} 1 = \sum_{i=0}^7 (n-1-i) = 8(n-1)-(0+\cdots+7)$.

Answer 2

Hint: As is often the case in math, you take it apart. The inner loop starts at $j=i+1$ and executes through $j=n-1$. How many values of $j$ is that? You are allowed to express it in terms of $i$ and $n$. Then you need to sum this expression over $i=0$ through $i=7$