Where does the O(n) come from in the time complexity of the closest pair algorithm?

Question

The time complexity of the closest pair problem is T(n) = 2T(n/2) + O(n). I understand that 2T(n/2) comes from the fact that the algorithm is applied to 2 sets of half the original's size, but why does the rest come out to O(n)? Thanks.

Answer 1

Any divide and conquer algorithm will consist of a recursive 'divide' component, and a 'merge' component where the recursed results are put together. The linear O(n) component in closet pair comes from merging the results from the 'divide' step into a merged answer.

Answer 2

Check out http://en.wikipedia.org/wiki/Closest_pair_of_points_problem which mentions clearly where the O(n) comes from (Planar case).