How to compute the time complexity of a triple nested loop represented by $\sum_{i=1}^{2n} \sum_{j=1}^{n} \sum_{k=j}^{n} i-j$

Question

var r = 0;
for(var i=1; i<=2*n; i++) {
  for(var j=1; j<=n; j++) {
    for(var k=j; k<=n; k++) {
      r = r + (i - j);
    }
  }
}

I'm trying to use summation to solve for it, but I'm having a bit of trouble.

I got this summation:

$$ \sum_{i=1}^{2n} \sum_{j=1}^{n} \sum_{k=j}^{n} i-j $$

But after trying to get a closed form for this, I got $-n^4 + n^2$, which is surely not the answer.

Could you guys help me?

Answer 1

$$\sum_{i=1}^{2n} \sum_{j=1}^{n} \sum_{k=j}^{n} i-j$$ $$\sum_{i=1}^{2n} \sum_{j=1}^{n} (i-j)\cdot(n-j+1)$$ $$\sum_{i=1}^{2n} \sum_{j=1}^{n} (ni-ij+i-nj+j^2-j)$$ $$\sum_{i=1}^{2n} (ni\cdot n-i\frac{n(n+1)}{2}+in-n\frac{n(n+1)}{2}+\frac{n(n+1)(2n+1)}{6}-\frac{n(n+1)}{2})$$ $$\sum_{i=1}^{2n} \left(i( n^2-\frac{n(n+1)}{2}+n)-\frac{n(n^2+3n+2)}{6}\right)$$

$$\sum_{i=1}^{2n} \left(i\frac{n(n+1)}{2}-\frac{n(n^2+3n+2)}{6}\right)$$ $$ \frac{2n(2n+1)}{2}\frac{n(n+1)}{2}-2n\frac{n(n^2+3n+2)}{6}=\frac23 n^4 + \frac12 n^3 - \frac16 n^2.$$

But this isn't the time complexity of the loop. It is the value of the triple summation in closed form.

Answer 2

$$\sum_{i=1}^{2n} \sum_{j=1}^{n} \sum_{k=j}^{n} i-j = \sum\limits_{i=1}^{2n} \sum\limits_{j=1}^n (i-j) \cdot (n-j+1) = \sum\limits_{i=1}^{2n} in^2 -\frac{in(n+1)}{2} + in - \frac{n^2(n+1)}{2} + \frac{n(n+1)(2n+1)}{6} - \frac{n(n+1)}{2} = \frac{2n^3(2n+1)}{2} - \frac{2n^2(n+1)(2n+1)}{4} + \frac{2n^2(2n+1)}{2} - \frac{2n^3(n+1)}{2} + \frac{2n^2(n+1)(2n+1)}{6} - \frac{2n^2(n+1)}{2} = \frac{2}{3}n^4 + \frac{n^3}{2} - \frac{n^2}{6} $$

Answer 3

According to Wolfram Alpha, $$ \sum_{i=1}^{2n} \sum_{j=1}^{n} \sum_{k=j}^{n} i-j = \frac23 n^4 + \frac12 n^3 - \frac16 n^2. $$

But that is not the time complexity of the loop. Instead, it is the value of the variable $r$ at the end of the loop.

To get the time complexity, ignore the values that are getting added or subtracted to $r$ inside the loop. You just want the big-O class of the total number of operations performed.

A simple trick to count the operations is to replace $i - j$ with $1.$ This will undercount the operations, but not by more than some constant factor, and big-O means you don't have to worry about the constant factor.