2.1

This loop can be expressed as the sum:

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

Reducing this, sum by sum from the rhs:

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

${\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 $1$ to $n$:-

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

And noting that:-

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

We continue our derivation thus:-

${\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 $n-1$ for $n$ gives us:-

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

${\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 $1$ and $n$:-

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

As before, let us substitute $n-1$ for $n$:-

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

${\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 $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 $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.

Return to Chapter 2