Difference between pages "Chapter 10" and "2.3"
(Created page with "Problems Back to Chapter List") |
(Created page with "<math>f(n) = (((n^2)(n+1)^2)/8) + n(n+1)(2n+1)/12</math> ---- This problem does appear to break down into a series of nested summations: <math> \displaystyle\sum_{i=1}^{n}\te...") |
||
Line 1: | Line 1: | ||
− | + | <math>f(n) = (((n^2)(n+1)^2)/8) + n(n+1)(2n+1)/12</math> | |
+ | ---- | ||
+ | This problem does appear to break down into a series of nested summations: | ||
+ | <math> | ||
+ | \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 | ||
+ | </math> | ||
− | Back to [[Chapter | + | 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_{j=1}^{i} | ||
+ | \displaystyle\sum_{k=j}^{i+j}(j+i-k) | ||
+ | </math> | ||
+ | |||
+ | 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> | ||
+ | |||
+ | Since <math>\displaystyle\sum_{k=start}^{end}(end-k) = \displaystyle\sum_{k=1}^{end-start}(k) </math> | ||
+ | |||
+ | So the summation boils down to | ||
+ | |||
+ | <math> | ||
+ | \displaystyle\sum_{i=1}^{n} | ||
+ | \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 <math>i*(i+1)/2</math>, <math>i</math> times. | ||
+ | |||
+ | <math> | ||
+ | \displaystyle\sum_{i=1}^{n}(i^2 * (i+1)/2) | ||
+ | </math> | ||
+ | |||
+ | which is | ||
+ | |||
+ | <math> | ||
+ | \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 {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}</math> | ||
+ | |||
+ | |||
+ | Time Complexity = O<math>({n}^{4})</math> | ||
+ | |||
+ | |||
+ | ---- | ||
+ | |||
+ | Back to [[Chapter 2]] |
Latest revision as of 18:49, 9 September 2020
[math]\displaystyle{ f(n) = (((n^2)(n+1)^2)/8) + n(n+1)(2n+1)/12 }[/math]
This problem does appear to break down into a series of nested summations:
[math]\displaystyle{ \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 }[/math]
In the last summation, the formula is independent of the iterator, which translates into adding the value 1, [math]\displaystyle{ j+i-k }[/math] times:
[math]\displaystyle{ \displaystyle\sum_{i=1}^{n} \displaystyle\sum_{j=1}^{i} \displaystyle\sum_{k=j}^{i+j}(j+i-k) }[/math]
Now the third summation goes from [math]\displaystyle{ j }[/math] to [math]\displaystyle{ i+j }[/math] the formula on closer examination reveals that
[math]\displaystyle{ \displaystyle\sum_{k=j}^{i+j}(j+i-k) }[/math] is [math]\displaystyle{ \displaystyle\sum_{k=1}^{i}(k) }[/math] which is equal to [math]\displaystyle{ i*(i+1)/2 }[/math]
Since [math]\displaystyle{ \displaystyle\sum_{k=start}^{end}(end-k) = \displaystyle\sum_{k=1}^{end-start}(k) }[/math]
So the summation boils down to
[math]\displaystyle{ \displaystyle\sum_{i=1}^{n} \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 [math]\displaystyle{ i*(i+1)/2 }[/math], [math]\displaystyle{ i }[/math] times.
[math]\displaystyle{ \displaystyle\sum_{i=1}^{n}(i^2 * (i+1)/2) }[/math]
which is
[math]\displaystyle{ \displaystyle\sum_{i=1}^{n}((i^3 + i^2)/2) }[/math]
[math]\displaystyle{ \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} }[/math]
Time Complexity = O[math]\displaystyle{ ({n}^{4}) }[/math]
Back to Chapter 2