Table of Contents

5.1 A First Recurrence: The Mergesort Algorithm

Divide and conquer algorithms are 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. Analyzing these problems usually involves solving recurrence relation that bounds the running time recursively in terms of the running time on smaller instances. Mergesort uses the same template as other divide and conquer algorithms to sort a given list of items:



So,let's T(n) denote the Mergesort's worst-case running times on input instances of size n.

Thus, 2 is the base case of the recurrence relation in Mergesort algorithm. We assume n is even. To solve for the overall running time of the algorithm, we need to solve the recurrences involved in the algorithm.

Approaches to Solving Recurrences

There are two general approaches to solving recurrences:

Unrolling the Mergesort Recurrence

Analyze the first few levels:

At the first level of recursion, we have a single problem of size n. It takes at most cn + time spent in all subsequent recursive calls.

At the next level, we have two problems of size n/2. Each takes at most cn/2 + time spent on subsequent recursive calls, for a total of at most cn.

A the third level, we have 4 problems each of size n/4, each taking time at most cn/4, for a total of at most cn.


Identifying the pattern :

At level j of the recursion, the number of subproblems has doubled j time

So, there are now a total of 2^j subproblems.

Each subproblem has in turn decreased its size by a factor of two j times

So,each subproblem has size n/2^j and takes time at most cn/2^j

Thus level j costs us at most 2^j*(cn/2^j) = cn


Summing over all levels of recursion :

We know that cn is the upper bound and applies to the total amount of work performed at each level.

The number of times the input must be halved to reduce its size from n to 2 is log2n

Thus, after summing the cn work over all logn levels of recursion, we get a total running time of O(nlogn).

So in brief, any function T(.) for which T(n) ≤ 2T(n/2) + cn is bounded by O(nlogn) when n>1.


Substituting into the Mergesort Recurrence

Let's suppose we think that T(n) ≤ cn log2n for all n ≥ 2 and we want to check whether it's true.

The above claims holds for n=2 since cn log2n = 2c and we know by the recurrence relation that T(2) ≤ c

Now, we assume by induction that T(m)≤ cmlog2m for all m < n, and we want to make prove this for T(n).

To do this, we just compute after appropriate substitutions:

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

= cn[(log2n)-1)] + cn

= (cn log2n) - cn + cn

= cn log2n

This argument establishes the bound T(n) we want, assuming it holds for smaller values m<n, and thus completes our induction proof.


An Approach Using Partial Substitution:

With this approach:

Guess the overall form of the solution without pinning down the exact values of all the constants and other parameters.

Suppose we believe that T(n) = O(nlogn) but we're not sure of the constant inside the T(.) notation. So,

T(n)≤ kn logbnfor some constant k and base b that we solve for.

We try to use the induction as follows:

T(n)≤ 2T(n/2) + cn ≤ 2k(n/2) logb(n/2) + cn

Let's now choose 2 as our base since it can help us simplify our expression.So,

T(n) ≤ 2k(n/2)log2(n/2) + cn
= 2k(n/2)[(log2n)-1] + cn

= kn[(log2n)-1] + cn

= (knlog2n) -kn + cn

Finally we ask ourselves if there is a choice of k that will make this expression be bounded by knlog2n

From the expression,it's obvious that we just need to choose a k that is at least as large as c, which gives us:

T(n) ≤ (knlog2n) -kn + cn ≤ knlog2n

Thus our proof is completed.


As useful as it is, our this section was really short and straightforward. I give a 9/10.