Difference between revisions of "TADM2E 2.2"

Revision as of 18:14, 11 September 2014

f(n) = n(n+1)(n+2)/3

Step by step explanation:

This loop can be expressed as the sum:

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

Reducing this, sum by sum from the rhs:

<math> \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} </math>

and order is O((n^3)/3)

Return to Algo-analysis-TADM2E ...