(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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\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, $j+i-k$ times:

$\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 $j$ to $i+j$ the formula on closer examination reveals that

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

So the summation boils down to

$\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 $i*(i+1)/2$, $i$ times.

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

which is

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

$\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$({n}^{4})$