Reference no: EM13943943

Lubo and Mike are building a "do all" robot in CS148 and have found that they have to fit two lego pieces side by side into an opening. The opening is x inches wide and the sum of the widths of the two pieces has to be exactly equal to the width of the opening, otherwise, their robot will fall apart during the demo. They have a huge collection of lego pieces of varying widths at their disposal and have to pick two pieces which satisfy the above constraint.

Since the Computer Science department at Brown believes in doing every- thing through a well defined algorithm, you should supply these poor guys an algorithm for doing the task, and one that is asymptotically efficient! So, here goes your exact problem.

You are given a set of n real numbers and another real number x. Describe a O(nlogn)-time algorithm that determines whether or not there exist two elements in S whose sum is exactly x. Hint : Doesn't the O(n log n) term make you feel that sorting is involved in some way?