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