Difference between revisions of "TADM2E 2.2"
(Recovering wiki) |
(Recovering wiki) |
||
| Line 5: | Line 5: | ||
This loop can be expressed as the sum: | This loop can be expressed as the sum: | ||
| − | + | <math> | |
\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=j}^{i+j}1 | \sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=j}^{i+j}1 | ||
| − | + | </math> | |
Reducing this, sum by sum from the rhs: | Reducing this, sum by sum from the rhs: | ||
| − | + | <math> | |
\begin{align} | \begin{align} | ||
| − | & | + | &\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=j}^{i+j}1=\\ |
| − | & | + | &\sum_{i=1}^{n}\sum_{j=1}^{i}i+j-j+1=\\ |
| − | & | + | &\sum_{i=1}^{n}\left(\sum_{j=1}^{i}i+\sum_{j=1}^{i}1\right)=\\ |
| − | & | + | &\sum_{i=1}^{n}\left(i\sum_{j=1}^{i}1+\sum_{j=1}^{i}1\right)=\\ |
| − | & | + | &\sum_{i=1}^{n}\left(\left(i+1\right)\sum_{j=1}^{i}1\right)=\\ |
| − | & | + | &\sum_{i=1}^{n}\left(i+1\right)i=\\ |
| − | & | + | &\sum_{i=1}^{n}i^2+i=\\ |
| − | & | + | &\sum_{i=1}^{n}i^2+\sum_{i=1}^{n}i=\\ |
| − | & | + | &\frac{n\left(n+1\right)\left(2n+1\right)}{6}+\frac{\left(n-1+1\right)\left(n+1\right)}{2}=\\ |
| − | & | + | &\frac{n\left(n+1\right)\left(2n+1\right)}{6}+\frac{n\left(n+1\right)}{2}=\\ |
| − | & | + | &\frac{n\left(n+1\right)\left(2n+1\right)+3n\left(n+1\right)}{6}=\\ |
| − | & | + | &\frac{n\left(n+1\right)\left(2n+1+3\right)}{6}=\\ |
| − | & | + | &\frac{n\left(n+1\right)\left(2n+4\right)}{6}=\\ |
| − | & | + | &\frac{2n\left(n+1\right)\left(n+2\right)}{6}=\\ |
| − | & | + | &\frac{n\left(n+1\right)\left(n+2\right)}{3} |
\end{align} | \end{align} | ||
| − | + | </math> | |
and order is O((n^3)/3) | and order is O((n^3)/3) | ||
Latest revision as of 18:23, 11 September 2014
f(n) = n(n+1)(n+2)/3
Step by step explanation:
This loop can be expressed as the sum:
$ \sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=j}^{i+j}1 $
Reducing this, sum by sum from the rhs:
$ \begin{align} &\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=j}^{i+j}1=\\ &\sum_{i=1}^{n}\sum_{j=1}^{i}i+j-j+1=\\ &\sum_{i=1}^{n}\left(\sum_{j=1}^{i}i+\sum_{j=1}^{i}1\right)=\\ &\sum_{i=1}^{n}\left(i\sum_{j=1}^{i}1+\sum_{j=1}^{i}1\right)=\\ &\sum_{i=1}^{n}\left(\left(i+1\right)\sum_{j=1}^{i}1\right)=\\ &\sum_{i=1}^{n}\left(i+1\right)i=\\ &\sum_{i=1}^{n}i^2+i=\\ &\sum_{i=1}^{n}i^2+\sum_{i=1}^{n}i=\\ &\frac{n\left(n+1\right)\left(2n+1\right)}{6}+\frac{\left(n-1+1\right)\left(n+1\right)}{2}=\\ &\frac{n\left(n+1\right)\left(2n+1\right)}{6}+\frac{n\left(n+1\right)}{2}=\\ &\frac{n\left(n+1\right)\left(2n+1\right)+3n\left(n+1\right)}{6}=\\ &\frac{n\left(n+1\right)\left(2n+1+3\right)}{6}=\\ &\frac{n\left(n+1\right)\left(2n+4\right)}{6}=\\ &\frac{2n\left(n+1\right)\left(n+2\right)}{6}=\\ &\frac{n\left(n+1\right)\left(n+2\right)}{3} \end{align} $
and order is O((n^3)/3)
Return to Algo-analysis-TADM2E ...
