Summation

• Jan 22nd 2010, 03:03 AM
Makall
Summation
The question is, how many multiplication and addition operations are required to determine:
$
\sum_{i=1}^{n}\ \sum_{j=1}^{i} a_{i}b_{j}\
$

And modify the sum to reduce the number of computations.

Are there (n-1) + n(i-1) addition operations (outer loop and inner loop respectively) and n*i multiplication operations?

Also, can it be rewritten as

$
n\sum_{j=1}^{i} a_{i}b_{j}\
$

Thanks.
• Jan 22nd 2010, 04:12 AM
In
$
\sum_{i=1}^{n}\ \sum_{j=1}^{i} a_{i}b_{j}\
$

The number of multiplications is:
$
\sum_{i=1}^{n}\ \sum_{j=1}^{i} 1 = \sum_{i=1}^{n}i = \frac {n(n+1)}{2}
$

$
(\sum_{i=1}^{n} i-1)-1 = \frac {(n-1)(n-1+1)}{2}-1= \frac {n(n-1)}{2}-1= \frac {n^2-n-2)}{2}
$

The way to reduce the number of operations is to notice that $a_{i}$ is common to all the terms after the first sum so we can rewrite as:
$
\sum_{i=1}^{n} a_{i} \sum_{j=1}^{i} b_{j}\
$

Now the number of multiplications is:
$
\sum_{i=1}^{n}1 = n
$

which is less than before.

$
$