Difference between revisions of "TADM2E 2.3"
(Recovering wiki) |
(Recovering wiki) |
||
| Line 3: | Line 3: | ||
This problem does appear to break down into a series of nested summations: | This problem does appear to break down into a series of nested summations: | ||
| − | + | <math> | |
\displaystyle\sum_{i=1}^{n}\text{ } | \displaystyle\sum_{i=1}^{n}\text{ } | ||
\displaystyle\sum_{j=1}^{i}\text{ } | \displaystyle\sum_{j=1}^{i}\text{ } | ||
\displaystyle\sum_{k=j}^{i+j}\text{ } | \displaystyle\sum_{k=j}^{i+j}\text{ } | ||
\displaystyle\sum_{l=1}^{j+i-k}1 | \displaystyle\sum_{l=1}^{j+i-k}1 | ||
| − | + | </math> | |
| − | In the last summation, the formula is independent of the iterator, which translates into adding the value 1, | + | In the last summation, the formula is independent of the iterator, which translates into adding the value 1, <math>j+i-k</math> times: |
| − | + | <math> | |
\displaystyle\sum_{i=1}^{n} | \displaystyle\sum_{i=1}^{n} | ||
\displaystyle\sum_{j=1}^{i} | \displaystyle\sum_{j=1}^{i} | ||
\displaystyle\sum_{k=j}^{i+j}(j+i-k) | \displaystyle\sum_{k=j}^{i+j}(j+i-k) | ||
| − | + | </math> | |
| − | Now the third summation goes from | + | Now the third summation goes from <math>j</math> to <math>i+j</math> the formula on closer examination reveals that |
| − | + | <math>\displaystyle\sum_{k=j}^{i+j}(j+i-k)</math> is <math> \displaystyle\sum_{k=1}^{i}(k) </math> which is equal to <math>i*(i+1)/2</math> | |
So the summation boils down to | So the summation boils down to | ||
| − | + | <math> | |
\displaystyle\sum_{i=1}^{n} | \displaystyle\sum_{i=1}^{n} | ||
\displaystyle\sum_{j=1}^{i} (i*(i+1)/2) | \displaystyle\sum_{j=1}^{i} (i*(i+1)/2) | ||
| − | + | </math> | |
| − | The formula in the second summation is independent of the iterator, which translates to adding | + | The formula in the second summation is independent of the iterator, which translates to adding <math>i*(i+1)/2</math>, <math>i</math> times. |
| − | + | <math> | |
\displaystyle\sum_{i=1}^{n}(i^2 * (i+1)/2) | \displaystyle\sum_{i=1}^{n}(i^2 * (i+1)/2) | ||
| − | + | </math> | |
which is | which is | ||
| − | + | <math> | |
\displaystyle\sum_{i=1}^{n}((i^3 + i^2)/2) | \displaystyle\sum_{i=1}^{n}((i^3 + i^2)/2) | ||
| − | + | </math> | |
| − | + | <math>\frac{1}{2} \left(\Sigma r^3 + \Sigma r^2\right) = | |
\frac{1}{2}\left(\frac{n^2\left(n+1\right)^2}{4} + | \frac{1}{2}\left(\frac{n^2\left(n+1\right)^2}{4} + | ||
\frac {n \left(n+1\right)\left(2n+1\right)}{6}\right) = | \frac {n \left(n+1\right)\left(2n+1\right)}{6}\right) = | ||
| − | \frac{n^2\left(n+1\right)^2}{8} + \frac {n \left(n+1\right)\left(2n+1\right)}{12} | + | \frac{n^2\left(n+1\right)^2}{8} + \frac {n \left(n+1\right)\left(2n+1\right)}{12}</math> |
| − | Time Complexity = O | + | Time Complexity = O<math>({n}^{4})</math> |
Revision as of 18:23, 11 September 2014
f(n) = (((n^2)(n+1)^2)/8) + n(n+1)(2n+1)/12
This problem does appear to break down into a series of nested summations:
$ \displaystyle\sum_{i=1}^{n}\text{ } \displaystyle\sum_{j=1}^{i}\text{ } \displaystyle\sum_{k=j}^{i+j}\text{ } \displaystyle\sum_{l=1}^{j+i-k}1 $
In the last summation, the formula is independent of the iterator, which translates into adding the value 1, $ j+i-k $ times:
$ \displaystyle\sum_{i=1}^{n} \displaystyle\sum_{j=1}^{i} \displaystyle\sum_{k=j}^{i+j}(j+i-k) $
Now the third summation goes from $ j $ to $ i+j $ the formula on closer examination reveals that
$ \displaystyle\sum_{k=j}^{i+j}(j+i-k) $ is $ \displaystyle\sum_{k=1}^{i}(k) $ which is equal to $ i*(i+1)/2 $
So the summation boils down to
$ \displaystyle\sum_{i=1}^{n} \displaystyle\sum_{j=1}^{i} (i*(i+1)/2) $
The formula in the second summation is independent of the iterator, which translates to adding $ i*(i+1)/2 $, $ i $ times.
$ \displaystyle\sum_{i=1}^{n}(i^2 * (i+1)/2) $
which is
$ \displaystyle\sum_{i=1}^{n}((i^3 + i^2)/2) $
$ \frac{1}{2} \left(\Sigma r^3 + \Sigma r^2\right) = \frac{1}{2}\left(\frac{n^2\left(n+1\right)^2}{4} + \frac {n \left(n+1\right)\left(2n+1\right)}{6}\right) = \frac{n^2\left(n+1\right)^2}{8} + \frac {n \left(n+1\right)\left(2n+1\right)}{12} $
Time Complexity = O$ ({n}^{4}) $
