1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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)$? $\endgroup$ Commented Aug 20, 2014 at 18:30
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Aug 20, 2014 at 18:37
  • $\begingroup$ 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? $\endgroup$ Commented Aug 20, 2014 at 18:52
  • $\begingroup$ @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.) $\endgroup$ Commented Aug 20, 2014 at 19:18
  • $\begingroup$ The edited question seems perfectly clear. It is asking for an algorithm to check whether a set of universal axioms holds in the structure. $\endgroup$ Commented Aug 25, 2014 at 11:41

1 Answer 1

3
$\begingroup$

for this algorithm it's enough to check sum of two smallest element is bigger than the maximum element.

We find Min1, Min2, Max.

if Min1 + Min2 < Max there is no. O(n) else all of them is true.

$\endgroup$
2
  • 1
    $\begingroup$ I can see that this is so, but this answer would be more helpful to others if you had sketched out a proof. A sentence would do. $\endgroup$ Commented Aug 20, 2014 at 19:28
  • $\begingroup$ Perhaps clearer: the three inequalities all hold iff the sum of the two smallest numbers exceeds the largest. $\endgroup$ Commented Aug 25, 2014 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.