Is it possible to find the number of triangles that can be formed from a list of lengths in better than (n choose 3) time?

Question

This relates to a larger problem I'm working on.

For example, let's say we're given a list

9 5 6 1

The possible triangles would have sides of length

(9,5,6)
(9,6,1)
(9,5,1)
(5,6,1)

and the ones that are valid (by the triangle inequality) are

(9,5,6)
(5,6,1)

Is it possible to find those valid ones in better-than-O(n choose 3) time?

Answer 1

In general case, the answer is no: imagine that you're given

 1, 1 - ε, 1 - 2 * ε, ..., 1 - (n - 1) * ε 

In that very case all combinations of 3 items

 n * (n - 1) * (n - 2) / 6 = O(n**3)

are distinct and make valid triangles and you have O(n**3) complexity just to enumerate (and output) them

Answer 2

First sort your list.

Now instead of doing complete O(n^3) search, we only need to search for pair of points in O(n^2) and find the third point ( maybe more than one point, so you need to check for lower bound and upper bound ) by doing a binary search.

So overall the new complexity is O(n^2 log(n))