Results 1 to 2 of 2

Thread: Summation

  1. #1
    Junior Member
    Joined
    Jan 2010
    Posts
    30

    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 (n-1) + n(i-1) 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jan 2010
    Posts
    17
    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} 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 $\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
    (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}
    $
    $\displaystyle
    = \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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How to do a Summation
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: May 14th 2011, 11:08 AM
  2. Summation
    Posted in the Pre-Calculus Forum
    Replies: 6
    Last Post: May 7th 2011, 06:23 AM
  3. summation
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Feb 2nd 2009, 08:17 AM
  4. Summation Help
    Posted in the Algebra Forum
    Replies: 9
    Last Post: Jan 31st 2009, 07:47 PM
  5. summation
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: Oct 8th 2008, 04:19 PM

Search Tags


/mathhelpforum @mathhelpforum