c - Total number of possible triangles from n numbers

Question

If n numbers are given, how would I find the total number of possible triangles? Is there any method that does this in less than O(n^3) time?

I am considering a+b>c, b+c>a and a+c>b conditions for being a triangle.

Answer 1

Assume there is no equal numbers in given n and it's allowed to use one number more than once. For example, we given a numbers {1,2,3}, so we can create 7 triangles:

1. 1 1 1
2. 1 2 2
3. 1 3 3
4. 2 2 2
5. 2 2 3
6. 2 3 3
7. 3 3 3

If any of those assumptions isn't true, it's easy to modify algorithm.

Here I present algorithm which takes O(n^2) time in worst case:

1. Sort numbers (ascending order). We will take triples ai <= aj <= ak, such that i <= j <= k.
2. For each i, j you need to find largest k that satisfy ak <= ai + aj. Then all triples (ai,aj,al) j <= l <= k is triangle (because ak >= aj >= ai we can only violate ak < a i+ aj).

Consider two pairs (i, j1) and (i, j2) j1 <= j2. It's easy to see that k2 (found on step 2 for (i, j2)) >= k1 (found one step 2 for (i, j1)). It means that if you iterate for j, and you only need to check numbers starting from previous k. So it gives you O(n) time complexity for each particular i, which implies O(n^2) for whole algorithm.

C++ source code:

int Solve(int* a, int n)
{
    int answer = 0;
    std::sort(a, a + n);

    for (int i = 0; i < n; ++i)
    {
        int k = i;

        for (int j = i; j < n; ++j)
        {
            while (n > k && a[i] + a[j] > a[k])
                ++k;

            answer += k - j;
        }
    }

    return answer;
}

Update for downvoters:

This definitely is O(n^2)! Please read carefully "An Introduction of Algorithms" by Thomas H. Cormen chapter about Amortized Analysis (17.2 in second edition). Finding complexity by counting nested loops is completely wrong sometimes. Here I try to explain it as simple as I could. Let's fix i variable. Then for that i we must iterate j from i to n (it means O(n) operation) and internal while loop iterate k from i to n (it also means O(n) operation). Note: I don't start while loop from the beginning for each j. We also need to do it for each i from 0 to n. So it gives us n * (O(n) + O(n)) = O(n^2).