TADM2E 2.3 - Revision history

Mikki at 19:46, 19 June 2017

2017-06-19T19:46:55Z

Rhaetional: Return link

2015-12-14T22:00:35Z

Return link

Parth: converted function to math notation

2015-10-15T09:38:10Z

converted function to math notation

Algowikiadmin: Recovering wiki

2014-09-11T18:23:59Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:14:15Z

Recovering wiki

New page

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:

<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>

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>

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>

← Older revision		Revision as of 19:46, 19 June 2017
Line 21:		Line 21:

	<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>		<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		So the summation boils down to

← Older revision		Revision as of 22:00, 14 December 2015
Line 49:		Line 49:

	Time Complexity = O<math>({n}^{4})</math>		Time Complexity = O<math>({n}^{4})</math>
		+
		+
		+	----
		+
		+	Return to [[Algo-analysis-TADM2E]] ...

@@ Line 1: / Line 1: @@
-f(n) = (((n^2)(n+1)^2)/8) + n(n+1)(2n+1)/12
+<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:

@@ Line 3: / Line 3: @@
 This problem does appear to break down into a series of nested summations:
-&lt;math&gt;
+<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
-&lt;/math&gt;
+</math>
-In the last summation, the formula is independent of the iterator, which translates into adding the value 1, &lt;math&gt;j+i-k&lt;/math&gt; times:
+In the last summation, the formula is independent of the iterator, which translates into adding the value 1, <math>j+i-k</math> times:
-&lt;math&gt;
+<math>
 \displaystyle\sum_{i=1}^{n}
 \displaystyle\sum_{j=1}^{i}
 \displaystyle\sum_{k=j}^{i+j}(j+i-k)
-&lt;/math&gt;
+</math>
-Now the third summation goes from &lt;math&gt;j&lt;/math&gt; to &lt;math&gt;i+j&lt;/math&gt; the formula on closer examination reveals that
+Now the third summation goes from <math>j</math> to <math>i+j</math> the formula on closer examination reveals that
-&lt;math&gt;\displaystyle\sum_{k=j}^{i+j}(j+i-k)&lt;/math&gt; is &lt;math&gt; \displaystyle\sum_{k=1}^{i}(k) &lt;/math&gt; which is equal to &lt;math&gt;i*(i+1)/2&lt;/math&gt;
+<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
-&lt;math&gt;
+<math>
 \displaystyle\sum_{i=1}^{n}
 \displaystyle\sum_{j=1}^{i} (i*(i+1)/2)
-&lt;/math&gt;
+</math>
-The formula in the second summation is independent of the iterator, which translates to adding &lt;math&gt;i*(i+1)/2&lt;/math&gt;, &lt;math&gt;i&lt;/math&gt; times.
+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.
-&lt;math&gt;
+<math>
 \displaystyle\sum_{i=1}^{n}(i^2 * (i+1)/2)
-&lt;/math&gt;
+</math>
 which is
-&lt;math&gt;
+<math>
 \displaystyle\sum_{i=1}^{n}((i^3 + i^2)/2)
-&lt;/math&gt;
+</math>
-&lt;math&gt;\frac{1}{2} \left(\Sigma r^3 + \Sigma r^2\right) =
+<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}&lt;/math&gt;
+\frac{n^2\left(n+1\right)^2}{8} + \frac {n \left(n+1\right)\left(2n+1\right)}{12}</math>
-Time Complexity = O&lt;math&gt;({n}^{4})&lt;/math&gt;
+Time Complexity = O<math>({n}^{4})</math>