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.

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}
$$
