Help analyzing the time-complexity of my algorithm So, (this is homework), we are given an array A, and we are asked to create a function where we return True/False if the array contains three elements which sum to a given value.
To formalize:
Given: A and some value, val
sum = A[i] + A[j] + A[k]
Note that: 1 < i < j < k
equals = False
for i=1 to n
    for j=i to n
        for k=j to n
            sum=A[i]+A[j]+A[k]
            if sum=val
                equals = True

The time complexity is obviously O(n^3) but I am having trouble making the formula. This is what I have so far:
T(n) = 1+n+n(n-i)+n(n-j)(n-i)+n(n-k)(n-i)(n-j)+????

Any help with analyzing the time complexity would be awesome.
Thanks in advance.
 A: I'll just count the number of times the sum=A[i]+A[j]+A[k] statement gets executed:
\begin{align*}
\sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^j 1
&= \sum_{i=1}^n \sum_{j=1}^i j \\
&= \sum_{i=1}^n \frac{i(i+1)}{2} \\
&= \frac{1}{2}\left[\sum_{i=1}^n i^2 + \sum_{i=1}^n i\right] \\
&= \frac{1}{2}\left[\frac{n(n + 1)(2n + 1)}{6} + \frac{n(n+1)}{2}\right] \\
&= \frac{1}{2}\left[\frac{n(n + 1)(2n + 1) + 3n(n+1)}{6}\right] \\
&= \frac{1}{2}\left[\frac{n(n + 1)((2n + 1) + 3)}{6}\right] \\
&= \frac{1}{2}\left[\frac{2n(n + 1)(n + 2)}{6}\right] \\
&= \frac{n(n + 1)(n + 2)}{6} \\
\end{align*}
Alternatively, you could notice that the number of tuples $(i,j,k)$ satisfying $1 \leq i \leq j \leq k \leq n$ is:
$$
\binom{n}{3} + 2\binom{n}{2} + \binom{n}{1}
= \frac{n(n - 1)(n - 2)}{6} + 2 \cdot \frac{n(n-1)}{2} + n
= \frac{n(n + 1)(n + 2)}{6}
$$
A: If you want a short-cut to get the bound, just count the number of times $i$ is between $1$ and $n/3$, and $j$ is between $n/3 + 1$ and $2n/3$, and $k$ is between $2n/3 + 1$ and $n$. That will give you a lower bound of approximately $n^3/9$ times the inner-most for loop body executes, and your algorithm is obviously $O(n^3)$ because each for loop executes at most $n$ times at its level, so $O(n^3)$ is a tight bound. Note, you can do better than $O(n^3)$ time for this problem, you can get it down to $O(n^2)$ either by sorting the array first, or if you use hashing.
