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?

  • $\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$ – Rick Decker Aug 20 '14 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. Aug 20 '14 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$ – David Richerby Aug 20 '14 at 18:52
  • $\begingroup$ Dear @RickDecker, i edit it. $\endgroup$ – user3661613 Aug 20 '14 at 19:11
  • $\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$ – David Richerby Aug 20 '14 at 19:18

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.

| cite | improve this answer | |
  • 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$ – Rick Decker Aug 20 '14 at 19:28
  • $\begingroup$ Perhaps clearer: the three inequalities all hold iff the sum of the two smallest numbers exceeds the largest. $\endgroup$ – András Salamon Aug 25 '14 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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