My algorithm is different from CLRS' -- is it wrong?

Question

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?

Answer 1

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.)

Answer 2

The core issue here is not a factual one, but one of expectations and (meta) logic:

But the solution they give in the Lecture Notes is [different from mine]. So my question is: why is my solution wrong? Is my algorithm incorrect or is it my analysis?

That's a glaring non sequitur!

1. There are infinitely many algorithms for every problem. The fact alone that you and somebody else have found different algorithms alone does not imply that either is wrong.

   Try to prove yours correct and analyse its cost to compare the two approaches!

2. We often know even multiple useful algorithms per problem. Every author picks one¹. What people consider straight-forward differs (a lot), and there are other motiviations for choosing one algorithm over another.

In algorithms (and many other places), comparing answers with an answer key is not good enough. You need a better strategy to check your work.

You have to provide your own proof of correctness and cost analysis. Of course, checking the solution from the book in the same way is advisable; books contain errors, always.

---

1. If the topic is not so fundamental that they think their book should include most if not all commonly used algorithms. This often happens with sorting or shortest paths.

Answer 3

Well, your algorithm is correct but there's just one small thing -- you need to modify binary search so that it does not return index $i$ itself when searching for an index $ j$ such that $S_i + S_j = k.$ For example, say you had $k=6$ and element 3 of the set ($S_3$) is $3$, your binary search must exclude index $3$ from its search space. This shouldn't be too tough to do though.