Divide and conquer - why does it work?

Question

I know that algorithms like mergesort and quicksort use the divide-and-conquer paradigm, but I'm wondering why does it work in lowering the time complexity...

why does usually a "divide and conquer" algorithm work better than a non-divide-and-conquer one?

Answer 1

Divide and conquer algorithms work faster because they end up doing less work.

Consider the classic divide-and-conquer algorithm of binary search: rather than looking at N items to find an answer, binary search ends up checking only Log2N of them. Naturally, when you do less work, you can finish faster; that's precisely what's going on with the divide-and-conquer algorithms.

Of course the results depend a lot on how well your strategy does at dividing the work: if the division is more or less fair at every step (i.e. you divide the work in half) you get the perfect Log2N speed. If, however, the dividing is not perfect (e.g. the worst case of quicksort, when it spends O(n^2) sorting the array because it eliminates only a single element at each iteration) then divide-and-conquer strategy is not helpful, as your algorithm does not reduce the amount of work.

Answer 2

Divide and conquer works, because the mathematics supports it!

Consider a few divide and conquer algorithms:

1) Binary search: This algorithm reduces your input space to half each time. It is intuitively clear that this is better than a linear search, as we would avoid looking at a lot of elements.

But how much better? We get the recurrence (note: this is recurrence for the worst case analysis):

T(n) = T(n/2) + O(1)

Mathematics implies that T(n) = Theta(log n). Thus this is exponentially better than a linear search.

2) Merge Sort: Here we divide into two (almost) equal halves, sort the halves and then merge them. Why should this be better than quadratic? This is recurrence:

T(n) = 2T(n/2) + O(n)

It can be mathematically shown (say using Master theorem) that T(n) = Theta(n log n). Thus T(n) is asymptotically better than quadratic.

Observe that the naive quicksort ends up giving us the recurrence for worst case as

T(n) = T(n-1) + O(n)

which mathematically, comes out to be quadratic, and in the worst case, isn't better than bubble sort (asymptotically speaking). But, we can show that in the average case, quicksort is O(n log n).

3 Selection Algorithm: This is a divide a conquer algorithm to find the k^th largest element. It is not at all obvious whether this algorithm is better than sorting (or even that it is not quadratic).

But mathematically, its recurrence(again worst case) comes out to be

T(n) = T(n/5) + T(7n/10 + 6) + O(n)

It can be shown mathematically that T(n) = O(n) and thus it is better than sorting.

Perhaps a common way to look at them:

You can look at algorithms as tree where each sub-problem becomes a sub-tree of the current and the node can be tagged with the amount of work done and then the total work can be added up for each node.

For binary search, the work is O(1) (just a compare), and one of the sub-trees, the work is 0, so the total amount of work is O(log n) (essentially a path, just like we do in binary search trees).

For merge-sort, for a node with k children, the work is O(k) (merge step). The work done at each level is O(n) (n, n/2 + n/2, n/4 + n/4 + n/4 + n/4 etc) and there are O(log n) levels, and so merge sort is O(n log n).

For quicksort, in the worst case the binary tree is actually a linked list, so work done is n+n-1 + ... + 1 = Omega(n^2).

For selection sort, I have no clue how to visualize it, but I believe looking at it as a tree with 3 children (n/5, 7n/10 and the remaining) might still help.