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.

  • 1
    Intuitively I'd reason that $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n) \approx 2 T(n/2) + \Theta(n)$ for large $n$, which has solution $T(n) = \Theta(n \log n)$, but I assume you want something more sophisticated.2012-03-05
  • 1
    The exact solution is $T(n) = n T(1) + c(n \lceil{\log_2 n}\rceil - 2^{\lceil{\log_2 n}\rceil} + n)$ but you don't need it for this problem. It's in Knuth's TAOCP and also in OEIS. http://oeis.org/A001855 , http://www.research.att.com/projects/OEIS?Anum=A0033142012-03-05
  • 1
    You can also find the solution to this problem using [the Akra-Bazzi method](http://en.wikipedia.org/wiki/Akra-Bazzi_method). Your example is also given at the bottom of the page there. I guess you could also use [the Master theorem](http://en.wikipedia.org/wiki/Master_theorem), although the rounding of $n/2$ does not quite fit in their formulas. (Computer science tends to be imprecise on these matters, and usually just regards $n/2$ as integral.)2012-03-05
  • 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