Chapter 5

Divide and conquer algorithms are algorithms that break the input into parts, solve the parts recursively, and then combine the solutions. When analyzing them, we will often look at recurrence relations, recursive functions that bound the running time of the algorithm.

The first algorithm we look at is the Mergesort Algorithm. In this algorithm, we break the input into two pieces, sort each recursively, and then merge the results together. The running time T(n) satisfies the recurrence relation T(n)⇐ 2T(n/2) + cn. To find a bound on the run time, we need to solve the recurrence relations.

We can solve recurrence relations in two ways: unrolling the recursion or substituting a possible solution. In the unrolling method, we analyze the first few levels, find a pattern, and sum over the levels of recursion. When trying substitution, we inductively prove our guess is correct. We can also use a weaker substitution if we are unsure of exact constants to help us find them. Solving the recurrence relation for mergesort shows the algorithm is O(nlogn).

Readability: 8