6
$\begingroup$

I'm learning algorithms by myself and am using the excellent Introduction to algorithms to do that. It has been quite a long time since I last studied math, so maybe the solution to my problem is trivial.

Exercise 4.3-5 asks to prove that $\Theta(n \lg n)$ is the solution to the "exact" recurrence for merge sort using the substitution method.

The recurrence is: $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$

Here is how I started to tackle the problem:

I need to prove that the recurrence is $O(n \lg n)$ and $\Omega(n \lg n)$ to prove that it is $\Theta(n \lg n)$. Let's begin with $O(n \lg n)$.

Let's assume that the bound $T(m) \leq cn \lg n$ holds for all $c > 0$, $m > 0$, $m > n$; in particular for $m = n/2$, yielding:

$ T(n/2) \leq cn/2 \lg(n/2) $

Substituting into the recurrence yields:

$\begin{aligned} T(n) &\leq c n/2 \lg(n/2) + c n/2 \lg(n/2) + \Theta(n) \\\\ &= cn \lg(n) - (cn - \Theta(n)) \end{aligned}$

And then I'm blocked, I guess I have to remove $\Theta(n)$ with something like $kn$ but it does not seem very rigorous.

  • 2
    There are standard ways to prove that floors and ceilings in recursive arguments can be ignored, if you only want an asymptotic solution. See Section 6 of [these notes](http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/99-recurrences.pdf). Once the floors and ceilings are gone, the recurrence falls immediately to recursion trees (or the Master theorem).2012-03-05

2 Answers 2

1

You can find a summary of the substitution method in this question statement and a discussion about the boundary conditions in an answer to the same question. The same material is available in section 4.3 on pages 83 and 84 of the third edition of the book. Especially interesting in this reference is the treatment of boundary conditions.

  • 2
    The statement of the Stack Overflow question that I referred to (and edited, by the way) refers to this material without giving the exact reference. It also contains additional relevant material. There are many questions about material in this book under this tag.2012-03-06
1

Your working is not exactly right, even before the point you got stuck.

You have replaced $\lceil n/2 \rceil$ and $\lfloor n/2 \rfloor$ by $n/2$, which is what you wanted to avoid, isn't it? (Otherwise we just use the recurrence $T(n) = 2T(n/2) + f(n)$).

We have the recurrence:

$T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + f(n)$

where $f(n) = \theta(n)$, i.e. there is some $C \gt 0$ such that $f(n) \le Cn$ for all $n$.

Suppose we want to show $T(n) = \mathcal{O}(n \log n)$.

(Note: the logarithm is to base $2$).

We try using strong induction.

Assume that $T(1) = 0$.

Suppose for all $k \lt n$, we have $T(k) \le D k\log k$, what $D$ is, we determine later.

Notice that $\lceil n/2 \rceil + \lfloor n/2 \rfloor = n$

There we have that

$T(n) \le Dn \log \lceil n/2 \rceil + f(n) \le Dn\log (\frac{n+1}{2}) + Cn$

Now $\log(n+1) \le \log n + \frac{1}{n}$ and so we get

$T(n) \le Dn\log n + D + Cn - Dn$

Now if we pick $D$ so that $Dn \gt Cn + D$ for all $n \gt 2$, we are done.

Picking $D \gt 2C$ will work and for this $D$, you can verify the base cases of $n=1,2$ easily.

Thus $T(n) = \mathcal{O}(n \log n)$.

Showing that $T(n) = \Omega(n\log n)$ might take more work.

  • 0
    @IntrepidTraveller: We are considering a mathematical recurrence, it could be space/time complexity or even something else (like number of comparisons). Besides, we can replace $T$ in the above post with $G$ where $G(n) = T(n) - T(1)$ and for that $G$, $G(1)$ is indeed $0$. $T(1) = 0$ is taken to simplify the math, and does not change the end result.2015-07-19