I'm trying to follow along with class notes that solves a triple summation for an algorithm for finding the maximum sum in a subinterval, with an array of length 14 (with 2 nested loops, 3 total loops) that begins like this:
$$\sum_{i=1}^n\sum_{j=i}^n \sum_{k=i}^j 1$$
Intuitively, I would think that this the function from this algorithm, say $f$ $\in O(n^3)$ since we have 3 nested loops and we seem to be running each loop close to $n$ times for each element in the array.
Would really appreciate any help, feeling quite stuck here and not sure how to properly interpret a problem like this.
Best Answer
Direct Approach
So we are looking at $\sum_{i=1}^n \sum_{j=i}^n (j - i + 1)$. If you think of the entries with indices $(i,j)$ as an $n \times n$, matrix, our summation uses the upper triangle of the matrix (where $j >i$) and the main diagonal (where $j=i$).
Note that along the diagonal, $j=i$ and so $i-j=0$ and the summand is all $1$, and there are exactly $n$ entries in the diagonal.
In the next diagonal band, there are $n-1$ entries, but there, $i = j+1$ so $i-j=1$ and the summand is $2$.
It's not hard to see the pattern, with each diagonal band having $i-j=d$ with $n-d$ elements, and the summand of $d+1$, resulting in the total sum of $(n-d)(d+1)$ for each such band.
Exact Approach
Here one alternative is to sum the result directly by changing the index in the inside summation to $k=j-i+1$. Then, since $i \le j \le n$, we have $1 \le j-i+1 = k \le n - i+1$ and the inner sum converts. A similar trick can be used on the outer sum letting $m = n-i+1$:
$$ \begin{split} S &= \sum_{i=1}^n \sum_{j=i}^n (j - i + 1) \quad \text{substitute } k = j-i+1\\ &= \sum_{i=1}^n \sum_{k=1}^{n-i+1} k \\ &= \sum_{i=1}^n \frac{(n-i+1)(n-i+2)}{2} \quad \text{substitute } m = n-i+1\\ &= \sum_{m=1}^n \frac{m(m+1)}{2} \\ &= \Theta\left(n^3\right) \end{split} $$
Direct Approach
So now we deal with $\sum_{d=0}^n (d+1)(n-d)$. Note that when $d \approx n/2$ we get quadratic terms in the sum since $(d+1) \approx n/2 \approx n - d$ and the term becomes roughly $(n/2)^2 = n^2/4$.
Thus, we have a linear number of terms which are at most quadratic, hence the sum is really $O\left(n^3\right)$.
Exact Approach
Here we can also sum directly to get a lower bound with an upper bound. Note that $$ \begin{split} \sum_{d=0}^n (d+1)(n-d) &= \sum_{d=0}^n \left[n + (n-1)d - d^2\right]\\ &= n \sum_{d=0}^n 1 + (n-1) \sum_{d=0}^n d - \sum_{d=0}^n d^2\\ &= n(n+1) + (n-1) \frac{n(n+1)}{2} - \frac{n(n+1)(2n+1)}{6} \\ &= n^3\left( \frac12 - \frac26 \right) + \Theta\left(n^2\right)\\ &= \frac16 n^3 + \Theta\left(n^2\right) \end{split} $$ which you could compute exactly if you wanted so. So the result is not just $O\left(n^3\right)$ (as is clear from the argument you present), but actually $\Theta\left(n^3\right)$.