# Linear-time algorithm for solving a set of inequalites

We have a set $A$ of $n$ distinct numbers. We want to determine for all $x,y,z \in A$ whether the following relations hold.

$$x+y>z\qquad x+z>y\qquad y+z>x$$

Anyone could describe $O(n)$ Algorithm?

• I edited your post slightly, so check that I haven't changed your intended meaning. Particularly, for a given set $A$ do you want to verify that the four relations hold for all possible triples of numbers $(x, y, z)$? Commented Aug 20, 2014 at 18:30
• Also, what does the relation "x,y>z" mean? Does it mean that "x>z" and "y>z"? I hope you'll edit the question to clarify. Once you've done that... What have you tried? What did you come up with? Please edit the question to show us your attempts and where you got stuck.
– D.W.
Commented Aug 20, 2014 at 18:37
• Why do you think it's possible to check each of the $n^3$ possible combinations of values of $x$, $y$ and $z$ in only $O(n)$ time? Commented Aug 20, 2014 at 18:52
• @user3661613 Still unclear. Do you mean "For each x,y,z in turn, we want to know if the inequalities hold" or "Is it true that the inequalities hold for every possible choice of x,y,z, or is there some x,y,z that makes them false"? An answer to the first question might look like "They're true for 4,5,2, true for 4,6,3, false for 4,6,1, ..." An answer to the second question would be either "Yes, they're true for all possibilities" or "No, they can be false (e.g., for 4,6,1)". (The specific examples in my comment are incorrect because I'd not noticed the inequalities had changed in the edit.) Commented Aug 20, 2014 at 19:18
• The edited question seems perfectly clear. It is asking for an algorithm to check whether a set of universal axioms holds in the structure. Commented Aug 25, 2014 at 11:41