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.

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.
