
Summation
The question is, how many multiplication and addition operations are required to determine:
$\displaystyle
\sum_{i=1}^{n}\ \sum_{j=1}^{i} a_{i}b_{j}\
$
And modify the sum to reduce the number of computations.
Are there (n1) + n(i1) addition operations (outer loop and inner loop respectively) and n*i multiplication operations?
Also, can it be rewritten as
$\displaystyle
n\sum_{j=1}^{i} a_{i}b_{j}\
$
Thanks.

In
$\displaystyle
\sum_{i=1}^{n}\ \sum_{j=1}^{i} a_{i}b_{j}\
$
The number of multiplications is:
$\displaystyle
\sum_{i=1}^{n}\ \sum_{j=1}^{i} 1 = \sum_{i=1}^{n}i = \frac {n(n+1)}{2}
$
The number of additions is:
$\displaystyle
(\sum_{i=1}^{n} i1)1 = \frac {(n1)(n1+1)}{2}1= \frac {n(n1)}{2}1= \frac {n^2n2)}{2}
$
The way to reduce the number of operations is to notice that $\displaystyle a_{i}$ is common to all the terms after the first sum so we can rewrite as:
$\displaystyle
\sum_{i=1}^{n} a_{i} \sum_{j=1}^{i} b_{j}\
$
Now the number of multiplications is:
$\displaystyle
\sum_{i=1}^{n}1 = n
$
which is less than before.
The number of additions is:
$\displaystyle
(n1) + \sum_{j=1}^{n1} j1
= (n1) + \frac {(n1)(n1+1)}{2}
= (n1) + \frac {n(n1)}{2}
$
$\displaystyle
= \frac{ (2n2)}{2} + \frac {n(n1)}{2}
= \frac{ (2n2) +n^2  n}{2} = \frac {n^2n2)}{2}
$
which is the same as before which makes sense because there are still the same number of terms to be added!