Algowikiadmin: Recovering wiki

2014-09-11T18:23:57Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:14:13Z

Recovering wiki

New page

2-1 ans

This loop can be expressed as the sum:

<math>
\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=1}^{j}1
</math>

Reducing this, sum by sum from the rhs:

<math>
\begin{align}
&\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=1}^{j}1 =\\
&\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}j =\\
&\sum_{i=1}^{n-1}\left(\sum_{j=1}^{n}j - \sum_{j=1}^{i}j\right) =\\
&\sum_{i=1}^{n-1}\left(\frac{n(n+1)}{2} - \frac{i(i+1)}{2}\right) =\\
&\frac{1}{2}\sum_{i=1}^{n-1}n^2+n-i^2-i =\\
&\frac{1}{2}\left((n-1)n^2 + (n-1)n - \left(\frac{n(n+1)(2n+1)}{6} - n^2\right) -
\left(\frac{n(n+1)}{2} - n\right)\right) =\\
&f(n) = \frac{n(n(n+1))}{2} - \frac{n(n+1)(2n+1)}{12} - \frac{n(n+1)}{4}
\end{align}
</math>

n=1 gives zero;
and order is O((n^3)/3)

== Alternative Derivation ==

<math>
\begin{align}
&mystery(n)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=1}^{j} 1\\
&=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}j\\
\end{align}
</math>

Taking the following well-known formula for the sum of the integers <math>1</math> to <math>n</math>:-

<math>
\sum_{x=1}^{n}x = \frac{1}{2}n(n + 1)
</math>

And noting that:-

<math>
\sum_{j=i+1}^{n}j = \sum_{j=1}^{n}j - \sum_{j=1}^{i}j
</math>

We continue our derivation thus:-

<math>
\begin{align}
&=\sum_{i=1}^{n-1}(\frac{1}{2}n(n+1) - \frac{1}{2}i(i+1))\\
&=\frac{1}{2}n(n-1)(n+1) - \frac{1}{2}\sum_{i=1}^{n-1}(i^2 + i)\\
\end{align}
</math>

Given our formula for the sum of integers, substituting <math>n-1</math> for <math>n</math> gives us:-

<math>
\sum_{x=1}^{n-1}x=\frac{1}{2}(n-1)((n-1)+1)=\frac{1}{2}n(n-1)
</math>

Thus continuing with our derivation:-

<math>
\begin{align}
&=\frac{1}{2}n(n-1)(n+1)- \frac{1}{2}\frac{1}{2}n(n-1) - \frac{1}{2}\sum_{i=1}^{n-1}i^2\\
&=\frac{1}{2}n(n-1)(n + 1 - \frac{1}{2}) - \frac{1}{2}\sum_{i=1}^{n-1}i^2\\
&=\frac{1}{2}n(n-1)(n + \frac{1}{2}) - \frac{1}{2}\sum_{i=1}^{n-1}i^2\\
\end{align}
</math>

Let us consider the well-known formula for the sum of the squares of the integers between <math>1</math> and <math>n</math>:-

<math>
\sum_{x=1}^{n}x^2=\frac{1}{6}n(n+1)(2n+1)
</math>

As before, let us substitute <math>n-1</math> for <math>n</math>:-

<math>
\sum_{x=1}^{n-1}x^2=\frac{1}{6}(n-1)((n-1)+1)(2(n-1)+1)=\frac{1}{6}n(n-1)(2n-1)
</math>

Substituting this into our derivation gives us:-

<math>
\begin{align}
&=\frac{1}{2}n(n-1)(n + \frac{1}{2}) - \frac{1}{2}\frac{1}{6}n(n-1)(2n - 1)\\
&=\frac{1}{2}n(n-1)(n + \frac{1}{2} - \frac{1}{6}(2n-1))\\
&=\frac{1}{2}n(n-1)(n + \frac{1}{2} - \frac{1}{3}n + \frac{1}{6})\\
&=\frac{1}{2}n(n-1)(\frac{2}{3}n + \frac{2}{3})\\
&=\frac{1}{3}n(n-1)(n+1)
\end{align}
</math>

Thus the solution is <math>mystery(n)=\frac{1}{3}n(n-1)(n+1)</math>. This is the equivalent to the solution given by the previous derivation.

The Big-Oh complexity of this function (ignoring constants) is O(n^3), as the RAM model dictates that each iteration of the increment of <math>r</math> is a time-step. We can ignore the first and last line's contribution to running time for the purposes of Big-Oh, as they do not contribute to the growth of the time taken with input size.

Return to [[Algo-analysis-TADM2E]] ...

@@ Line 3: / Line 3: @@
 This loop can be expressed as the sum:
-&lt;math&gt;
+<math>
 \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=1}^{j}1
-&lt;/math&gt;
+</math>
 Reducing this, sum by sum from the rhs:
-&lt;math&gt;
+<math>
 \begin{align}
-&amp;\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=1}^{j}1 =\\
+&\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=1}^{j}1 =\\
-&amp;\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}j =\\
+&\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}j =\\
-&amp;\sum_{i=1}^{n-1}\left(\sum_{j=1}^{n}j - \sum_{j=1}^{i}j\right) =\\
+&\sum_{i=1}^{n-1}\left(\sum_{j=1}^{n}j - \sum_{j=1}^{i}j\right) =\\
-&amp;\sum_{i=1}^{n-1}\left(\frac{n(n+1)}{2} - \frac{i(i+1)}{2}\right) =\\
+&\sum_{i=1}^{n-1}\left(\frac{n(n+1)}{2} - \frac{i(i+1)}{2}\right) =\\
-&amp;\frac{1}{2}\sum_{i=1}^{n-1}n^2+n-i^2-i =\\
+&\frac{1}{2}\sum_{i=1}^{n-1}n^2+n-i^2-i =\\
-&amp;\frac{1}{2}\left((n-1)n^2 + (n-1)n - \left(\frac{n(n+1)(2n+1)}{6} - n^2\right) -
+&\frac{1}{2}\left((n-1)n^2 + (n-1)n - \left(\frac{n(n+1)(2n+1)}{6} - n^2\right) -
      \left(\frac{n(n+1)}{2} - n\right)\right) =\\
-&amp;f(n) = \frac{n(n(n+1))}{2} - \frac{n(n+1)(2n+1)}{12} - \frac{n(n+1)}{4}
+&f(n) = \frac{n(n(n+1))}{2} - \frac{n(n+1)(2n+1)}{12} - \frac{n(n+1)}{4}
 \end{align}
-&lt;/math&gt;
+</math>
 n=1 gives zero;
@@ Line 28: / Line 28: @@
 == Alternative Derivation ==
-&lt;math&gt;
+<math>
 \begin{align}
-&amp;mystery(n)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=1}^{j} 1\\
+&mystery(n)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=1}^{j} 1\\
-&amp;=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}j\\
+&=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}j\\
 \end{align}
-&lt;/math&gt;
+</math>
-Taking the following well-known formula for the sum of the integers &lt;math&gt;1&lt;/math&gt; to &lt;math&gt;n&lt;/math&gt;:-
+Taking the following well-known formula for the sum of the integers <math>1</math> to <math>n</math>:-
-&lt;math&gt;
+<math>
 \sum_{x=1}^{n}x = \frac{1}{2}n(n + 1)
-&lt;/math&gt;
+</math>
 And noting that:-
-&lt;math&gt;
+<math>
 \sum_{j=i+1}^{n}j = \sum_{j=1}^{n}j - \sum_{j=1}^{i}j
-&lt;/math&gt;
+</math>
 We continue our derivation thus:-
-&lt;math&gt;
+<math>
 \begin{align}
-&amp;=\sum_{i=1}^{n-1}(\frac{1}{2}n(n+1) - \frac{1}{2}i(i+1))\\
+&=\sum_{i=1}^{n-1}(\frac{1}{2}n(n+1) - \frac{1}{2}i(i+1))\\
-&amp;=\frac{1}{2}n(n-1)(n+1) - \frac{1}{2}\sum_{i=1}^{n-1}(i^2 + i)\\
+&=\frac{1}{2}n(n-1)(n+1) - \frac{1}{2}\sum_{i=1}^{n-1}(i^2 + i)\\
 \end{align}
-&lt;/math&gt;
+</math>
-Given our formula for the sum of integers, substituting &lt;math&gt;n-1&lt;/math&gt; for &lt;math&gt;n&lt;/math&gt; gives us:-
+Given our formula for the sum of integers, substituting <math>n-1</math> for <math>n</math> gives us:-
-&lt;math&gt;
+<math>
 \sum_{x=1}^{n-1}x=\frac{1}{2}(n-1)((n-1)+1)=\frac{1}{2}n(n-1)
-&lt;/math&gt;
+</math>
 Thus continuing with our derivation:-
-&lt;math&gt;
+<math>
 \begin{align}
-&amp;=\frac{1}{2}n(n-1)(n+1)- \frac{1}{2}\frac{1}{2}n(n-1) - \frac{1}{2}\sum_{i=1}^{n-1}i^2\\
+&=\frac{1}{2}n(n-1)(n+1)- \frac{1}{2}\frac{1}{2}n(n-1) - \frac{1}{2}\sum_{i=1}^{n-1}i^2\\
-&amp;=\frac{1}{2}n(n-1)(n + 1 - \frac{1}{2}) - \frac{1}{2}\sum_{i=1}^{n-1}i^2\\
+&=\frac{1}{2}n(n-1)(n + 1 - \frac{1}{2}) - \frac{1}{2}\sum_{i=1}^{n-1}i^2\\
-&amp;=\frac{1}{2}n(n-1)(n + \frac{1}{2}) - \frac{1}{2}\sum_{i=1}^{n-1}i^2\\
+&=\frac{1}{2}n(n-1)(n + \frac{1}{2}) - \frac{1}{2}\sum_{i=1}^{n-1}i^2\\
 \end{align}
-&lt;/math&gt;
+</math>
-Let us consider the well-known formula for the sum of the squares of the integers between &lt;math&gt;1&lt;/math&gt; and &lt;math&gt;n&lt;/math&gt;:-
+Let us consider the well-known formula for the sum of the squares of the integers between <math>1</math> and <math>n</math>:-
-&lt;math&gt;
+<math>
 \sum_{x=1}^{n}x^2=\frac{1}{6}n(n+1)(2n+1)
-&lt;/math&gt;
+</math>
-As before, let us substitute &lt;math&gt;n-1&lt;/math&gt; for &lt;math&gt;n&lt;/math&gt;:-
+As before, let us substitute <math>n-1</math> for <math>n</math>:-
-&lt;math&gt;
+<math>
 \sum_{x=1}^{n-1}x^2=\frac{1}{6}(n-1)((n-1)+1)(2(n-1)+1)=\frac{1}{6}n(n-1)(2n-1)
-&lt;/math&gt;
+</math>
 Substituting this into our derivation gives us:-
-&lt;math&gt;
+<math>
 \begin{align}
-&amp;=\frac{1}{2}n(n-1)(n + \frac{1}{2}) - \frac{1}{2}\frac{1}{6}n(n-1)(2n - 1)\\
+&=\frac{1}{2}n(n-1)(n + \frac{1}{2}) - \frac{1}{2}\frac{1}{6}n(n-1)(2n - 1)\\
-&amp;=\frac{1}{2}n(n-1)(n + \frac{1}{2} - \frac{1}{6}(2n-1))\\
+&=\frac{1}{2}n(n-1)(n + \frac{1}{2} - \frac{1}{6}(2n-1))\\
-&amp;=\frac{1}{2}n(n-1)(n + \frac{1}{2} - \frac{1}{3}n + \frac{1}{6})\\
+&=\frac{1}{2}n(n-1)(n + \frac{1}{2} - \frac{1}{3}n + \frac{1}{6})\\
-&amp;=\frac{1}{2}n(n-1)(\frac{2}{3}n + \frac{2}{3})\\
+&=\frac{1}{2}n(n-1)(\frac{2}{3}n + \frac{2}{3})\\
-&amp;=\frac{1}{3}n(n-1)(n+1)
+&=\frac{1}{3}n(n-1)(n+1)
 \end{align}
-&lt;/math&gt;
+</math>
-Thus the solution is &lt;math&gt;mystery(n)=\frac{1}{3}n(n-1)(n+1)&lt;/math&gt;. This is the equivalent to the solution given by the previous derivation.
+Thus the solution is <math>mystery(n)=\frac{1}{3}n(n-1)(n+1)</math>. This is the equivalent to the solution given by the previous derivation.
-The Big-Oh complexity of this function (ignoring constants) is O(n^3), as the RAM model dictates that each iteration of the increment of &lt;math&gt;r&lt;/math&gt; is a time-step. We can ignore the first and last line's contribution to running time for the purposes of Big-Oh, as they do not contribute to the growth of the time taken with input size.
+The Big-Oh complexity of this function (ignoring constants) is O(n^3), as the RAM model dictates that each iteration of the increment of <math>r</math> is a time-step. We can ignore the first and last line's contribution to running time for the purposes of Big-Oh, as they do not contribute to the growth of the time taken with input size.
 Return to [[Algo-analysis-TADM2E]] ...

TADM2E 2.1 - Revision history

Algowikiadmin: Recovering wiki

Algowikiadmin: Recovering wiki