Difference between pages "Chapter 9" and "2.1"
(Created page with "Problems Back to Chapter List") |
(Created page with " 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...") |
||
Line 1: | Line 1: | ||
− | |||
+ | 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 [[Chapter 2]] |
Latest revision as of 19:25, 8 September 2020
This loop can be expressed as the sum:
[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ 1 }[/math] to [math]\displaystyle{ n }[/math]:-
[math]\displaystyle{ \sum_{x=1}^{n}x = \frac{1}{2}n(n + 1) }[/math]
And noting that:-
[math]\displaystyle{ \sum_{j=i+1}^{n}j = \sum_{j=1}^{n}j - \sum_{j=1}^{i}j }[/math]
We continue our derivation thus:-
[math]\displaystyle{ \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]\displaystyle{ n-1 }[/math] for [math]\displaystyle{ n }[/math] gives us:-
[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ 1 }[/math] and [math]\displaystyle{ n }[/math]:-
[math]\displaystyle{ \sum_{x=1}^{n}x^2=\frac{1}{6}n(n+1)(2n+1) }[/math]
As before, let us substitute [math]\displaystyle{ n-1 }[/math] for [math]\displaystyle{ n }[/math]:-
[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ 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]\displaystyle{ 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 Chapter 2