Summation

**Makall** · January 22nd 2010, 02:03 AM

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.

**Suhada** · January 22nd 2010, 03: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} $
The number of additions is:
$ (\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.

The number of additions is:
$ (n-1) + \sum_{j=1}^{n-1} j-1 = (n-1) + \frac {(n-1)(n-1+1)}{2} = (n-1) + \frac {n(n-1)}{2} $
$ = \frac{ (2n-2)}{2} + \frac {n(n-1)}{2} = \frac{ (2n-2) +n^2 - n}{2} = \frac {n^2-n-2)}{2} $
which is the same as before which makes sense because there are still the same number of terms to be added!

Thread: Summation

LinkBack

Thread Tools

Display

Summation

Similar Math Help Forum Discussions

How to do a Summation

Summation

summation

Summation Help

summation

Search Tags