[Solved]: My algorithm is different from CLRS' -- is it wrong?

Problem Detail: 

Exercise 2.3-7 from "Introduction to Algorithms" by Cormen et al. Third Edition, states:

Describe a O(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether of not there exist two elements in S whose sum is exactly x.

At first, I had no idea how to solve it since I thought you couldn't access elements of a set by index, but assuming you could, here was my solution:

First off, we sort the set S, and then for every element y in S, we search if x - y exists in S. If x - y exists then we are done, otherwise continue the process until we have looked at all elements in S.

Since we sort at the beginning it's O(n log n) and then we perform a binary search for every element, so total cost would be O(n log n) + O(n log n), therefore O(n log n).

But the solution they give in the Lecture Notes is:

The following algorithm solves the problem:

1. Sort the elements in S.
2. Form the set S'= {z : z = x − y for some y ∈ S}.
3. Sort the elements in S'.
4. If any value in S appears more than once, remove all but one instance. Do the same for S'.
5. Merge the two sorted sets S and S'.
6. There exist two elements in S whose sum is exactly x if and only if the same value appears in consecutive positions in the merged output.

And they go on to say:

Steps 1 and 3 require O(n lg n) steps. Steps 2, 4, 5, and 6 require O(n) steps. Thus the overall running time is O(n lg n).

So obviously they assume a set is just a regular array (you can access elements by index and the elements don't have to be unique). (And just to clarify my assumption, from the beginning of the book up to this point, they haven't put forth their definition of set, so it was easy to assume they were referring to an actual set).

It seems to me that even though their solution is O(n log n), my solution not only does it reduce the "hidden costs" greatly, it's also much more straightforward than theirs.

(To account for the possibility of repeated elements, nothing needs to be modified since the current y is not inside the searching subarray)

I've checked the published erratas (I know it wouldn't be a mistake per se anyway, but I thought it might've said something there), and there is nothing. So my question is: why is my solution wrong? Is my algorithm incorrect or is it my analysis?

Asked By : Paul McCullough

Answered By : Hendrik Jan

You are right, there is a assuption that the set is available as an unsorted array, but I think that most set representations will allow you to obtain all elements in linear time. I also agree with you that your solution is straightforward, and uses no funny tricks.

I guess their solution is to impress you that only sorting and merging is needed, no such complicated things as binary search. (insert smiley here.) Perhaps binary search was not yet introduced at that point?

To illustrate the point Raphael makes — there are infinitely many implementations — here is mine. I believe it is correct, and uses only one sort, and a linear pass over the array. So: sort the array (from small to large). To check whether $y,z\in S$ exist such that $y+z=x$ move over the array from both sides. If the sum of the two elements of the array is larger than $x$ move the larger element one down, if it is less than $x$ move the smaller element one up. (How does this compare to your proposal?)

Nevertheless I would not consider their solution as incorrect. I like to think that it is good to have several solutions available. In some circumstances one implementation may outperform another. E.g., if the set was to be given as a sorted linked list, your solution would be hard to implement. (And mine only works if the list is doubly linked.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/58263

3.2K people like this

 Download Related Notes/Documents