Algorithm Notes: Divide and Conquer

Divide and conquer is a strategy that helps simplify solving a complex problem. It begins by dividing a problem into subproblems. It then keeps doing that until the subproblem is trivial to solve. In the end the outcome of each subproblem are assembled backwards and eventually lead to the result of the whole problem.

Divide and conquer sometimes looks like a magic to me. By simply dividing it into subproblems, the whole problem is solved with a time complexity that is lighter than the intuitive impression of the whole problem's time complexity. Of course, if we parallelize subproblems, this makes perfect sense. However, when talking about algorithms, we usually don't assume the existence of special computational power supports.

In fact, the time complexity of a divide-and-conquer operation depends on the time of each sub-operation. The formula is not intuitive to understand so let's just treat it as a magic. Generally, given a problem of size \(n\), we divide it into \(a\) subproblems with each of size \(n/b\), and then assemble the results of subproblems in \(O(n^d)\) time, where \(a,b,d > 0\). The final time complexity follows the formula below:

$$ T(n)=\begin{cases} O(n^d) &\text{if } d > log_ba \\ O(n^dlogn) &\text{if } d = log_ba \\ O(n^{log_ba}) &\text{if } d < log_ba . \end{cases} $$

Merge sort

Let's look at one typical example of divide and conquer, the merge sort. The basic idea of merge sort is to recursively divide an unsorted array into two sub-arrays, sort each sub-array respectively, and then merge the two sorted sub-arrays into one sorted array. With the above formula, we then have \(a=2, b=2, d=1\), and thus the time complexity is \(O(n^dlogn)\), that is, \(O(nlogn)\). In fact, \(O(nlogn)\) is the optimal time for sorting.

In some cases the process of merge sort is at least as interesting as its result. Looking into the process, from the perspective of each element, the nature of merge sort is to recursively move all smaller elements after it within the scope (i.e., the subproblem) to be ahead of it. One interesting coding problem [“Count of Smaller Numbers After Self”] (https://leetcode.com/problems/count-of-smaller-numbers-after-self/) asks exactly such process of merge sort.

Contents