# 2.3

Jump to navigation Jump to search

${\displaystyle 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:

${\displaystyle \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}$

In the last summation, the formula is independent of the iterator, which translates into adding the value 1, ${\displaystyle j+i-k}$ times:

${\displaystyle \displaystyle \sum _{i=1}^{n}\displaystyle \sum _{j=1}^{i}\displaystyle \sum _{k=j}^{i+j}(j+i-k)}$

Now the third summation goes from ${\displaystyle j}$ to ${\displaystyle i+j}$ the formula on closer examination reveals that

${\displaystyle \displaystyle \sum _{k=j}^{i+j}(j+i-k)}$ is ${\displaystyle \displaystyle \sum _{k=1}^{i}(k)}$ which is equal to ${\displaystyle i*(i+1)/2}$

Since ${\displaystyle \displaystyle \sum _{k=start}^{end}(end-k)=\displaystyle \sum _{k=1}^{end-start}(k)}$

So the summation boils down to

${\displaystyle \displaystyle \sum _{i=1}^{n}\displaystyle \sum _{j=1}^{i}(i*(i+1)/2)}$

The formula in the second summation is independent of the iterator, which translates to adding ${\displaystyle i*(i+1)/2}$, ${\displaystyle i}$ times.

${\displaystyle \displaystyle \sum _{i=1}^{n}(i^{2}*(i+1)/2)}$

which is

${\displaystyle \displaystyle \sum _{i=1}^{n}((i^{3}+i^{2})/2)}$

${\displaystyle {\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}}}$

Time Complexity = O${\displaystyle ({n}^{4})}$

Back to Chapter 2