Divide and conquer refers to a class of algorithmic techniques in which one breaks the input into several parts, solves the problem in each part recursively, and then combines the solutions to these subproblems into an overall solution. In many cases, it can be a simple and powerful method.

First Intuitive: MergeSort

MergeSort sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results.

On each successive call of mergersort, the input will be divided by half. We keep dividing them until the input has the size of 2.

Let T(n) denote the worst-case running time on input instance of size n.

• The algorithm takes O(n) time to split the inputs into two halves.
• The algorithm takes T(n/2) to solve each half.
• The algorithm takes O(n) to combine the solutions.

It's easy to observe that the running time follows a recurrence relation

$$ T(n) ≤ 2T(n/2) + cn $$

when n > 2, and $T(2) \le c$

we can also say that

				$T(n) ≤ 2T(n/2) + O(n)$ 

Approaches to Solving Recurrence

• Unroll the recurrence: accounting for the running time across the first few levels, and identify a pattern that can be continued as the recursion expands
• Substitute the recurrence: Guess for a solution and substitute it into the recurrence relation to check whether it works with an argument by induction on n.

Unrolling MergeSort:

1. Analyzing first few levels:

   first, second, third levels have size of n, n/2, n/4 with total of at most cn

2. Identifying a pattern

   At level j of the recursion, the number of subproblems has doubled j times, so there are now a total of $2^j$ **but with shrunk sizes. Level j contributes a total of at most $2j(cn/2j) = cn$ **to the total running time.

3. Summing over all levels of recursion The number of times the input must be halved in order to reduce its size from n to 2 is So summing the cn work over log n levels of recursion, we get a total running time of $O(n log n).$

Substituting MergeSort: