Define algorithm using divide and conquer paradigm

Question

Q:Describe a Θ(n lg n)-time algorithm that, given a set S of n integers, determines which two elements in S have the smallest difference.

(From what i understand, we first apply merge sort to our list which should take theta(n log n) time. Now as the numbers are sorted, we can compare adjacent members and record their differences keeping track(possibly using an array). This should take theta(n) time. Therefore the overall running time will still be of order theta(n log n).Is this explanation valid?

Answer 1

This isn't recursive, but:

Since sorting takes $\Theta(n \log n)$ time, sort $S$.

Then go through the sorted list, looking at the difference between consecutive items. The smallest difference is what you want. This last step takes $\Theta(n)$ time, so the total time is still $\Theta(n \log n)$.

Answer 2

For such problem, always start from an ad-hoc method and check the complexity. Then improve the solution to $\Theta(n log n)$.

Without thinking, we do a subtraction among n numbers, so we have $nXn$ numbers of difference, than look for it. The complexity is $\Theta(n^2$. Now, we want to improve it.

The first step to improve naive algorithm is to impose an order on the set of n integers. If the set S is ordered, we only need to look for the difference of two neighbouring pairs. The complexity of finding the smallest of the difference from the ordered set is $O(n)$. To put the set S into order, we need to use a merge sort, which is of O(nlog n).

The final algorithm is: 1) use merge sort to sort set S into order; 2) go through ordered set, caculate the difference of neighboring two integers,and comparing to choose the smallest one. The total complexity is $\Theta(n log n)$ from merge sort.