Difference between pages "Chapter 10" and "2.3"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
(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:
Problems
+
<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 List]]
+
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