# 2.1

This loop can be expressed as the sum:

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

Reducing this, sum by sum from the rhs:

{\displaystyle {\begin{aligned}&\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{aligned}}}

n=1 gives zero; and order is O((n^3)/3)

## Alternative Derivation

{\displaystyle {\begin{aligned}&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{aligned}}}

Taking the following well-known formula for the sum of the integers ${\displaystyle 1}$ to ${\displaystyle n}$:-

${\displaystyle \sum _{x=1}^{n}x={\frac {1}{2}}n(n+1)}$

And noting that:-

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

We continue our derivation thus:-

{\displaystyle {\begin{aligned}&=\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{aligned}}}

Given our formula for the sum of integers, substituting ${\displaystyle n-1}$ for ${\displaystyle n}$ gives us:-

${\displaystyle \sum _{x=1}^{n-1}x={\frac {1}{2}}(n-1)((n-1)+1)={\frac {1}{2}}n(n-1)}$

Thus continuing with our derivation:-

{\displaystyle {\begin{aligned}&={\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{aligned}}}

Let us consider the well-known formula for the sum of the squares of the integers between ${\displaystyle 1}$ and ${\displaystyle n}$:-

${\displaystyle \sum _{x=1}^{n}x^{2}={\frac {1}{6}}n(n+1)(2n+1)}$

As before, let us substitute ${\displaystyle n-1}$ for ${\displaystyle n}$:-

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

Substituting this into our derivation gives us:-

{\displaystyle {\begin{aligned}&={\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{aligned}}}

Thus the solution is ${\displaystyle mystery(n)={\frac {1}{3}}n(n-1)(n+1)}$. 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 ${\displaystyle r}$ 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.