Help analyzing the time-complexity of my algorithm

Question

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.

Answer 1

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

Answer 2

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.