[Solved]: Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem

Problem Detail: 

The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we happily go from

$\qquad T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n)$

to

$\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n)$

considering only $n=2^k$. We assure ourselved that this step is valid -- that is, $T \in \Theta(T')$ -- because $T$ behaves "nicely". In general, we assume $n=b^k$ for $b$ the common denominator.

It is easy to construct recurrences which do not allow this simplification by using vicious $f$. For example, above recurrence for $T\,$/$\,T'$ with

$\qquad f(n) = \begin{cases} 1 &, n=2^k \\ n &, \text{else} \end{cases}$

will yield $\Theta(n)$ by using the Master theorem in the usual way, but there is clearly a subsequence that grows like $\Theta(n \log n)$. See here for another, more contrived example.

How can we make this "nicely" rigorous? I am quite certain that monotonicity is sufficient, but not even the simple Mergesort recurrence is monotone; there is a periodic component (which is dominated asymptotically). Is it enough to investigate $f$, and what are necessary and sufficient conditions on $f$ that ensure the Master theorem works?

Asked By : Raphael

Answered By : Yuval Filmus

Throughout this answer, we assume $f$ and $T$ are non-negative. Our proof works whenever $f = \Theta(g)$ for some monotone $g$. This includes your Mergesort example, in which $f=\Theta(n)$, and any function which has polynomial growth rate (or even $\Theta(n^a \log^b n)$).

Let's consider first the case that $f$ is monotone non-decreasing (we'll relax this assumption later). We concentrate on your sample recurrence $$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n). $$ This recurrence needs two base cases, $T(0)$ and $T(1)$. We make the assumption that $T(0) \leq T(1)$, which we also relax later on.

I claim that $T(n)$ is monotone non-decreasing. We prove by complete induction that $T(n+1) \geq T(n)$. This is given for $n = 0$, so let $n \geq 1$. We have $$ \begin{align*} T(n+1) &= T(\lfloor (n+1)/2 \rfloor) + T(\lceil (n+1)/2 \rceil) + f(n+1) \\ &\geq T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n) = T(n). \end{align*} $$ This implies that $$ T(2^{\lfloor \log_2 n \rfloor}) \leq T(n) \leq T(2^{\lceil \log_2 n \rfloor}). $$ So if $T(2^m) = \Theta(T(2^{m+1}))$, we're done. This is always the case if the solution for powers of two is of the form $T(n) = \Theta(n^a \log^b n)$.

Now let's relax the assumption that $T(0) \leq T(1)$. Consider a new recurrence $T'$ defined in exactly the same way, only $T'(0) = T'(1) = \min(T(0),T(1))$. We can prove by induction that $T'(n) \leq T(n)$. Similarly, we can define a new recurrence $T''$ satisfying $T''(0) = T''(1) = \max(T(0),T(1))$, and then $T(n) \leq T''(n)$. Invoking the Master theorem, we see that $T'=\Theta(h)$ and $T''=\Theta(h)$ for the same function $h$, and so $T = \Theta(h)$ as well.

Now let's relax the assumption that $f$ is monotone. Suppose that $f = \Theta(g)$ for some monotone function $g$. Thus $cg(n) \leq f(n) \leq Cg(n)$ for some $c,C>0$ and $n$ large enough. We assume for simplicity that $n=0$; the general case can be handled as in the previous paragraph. Again we define two recurrences $T',T''$ by replacing $f$ with $cg,Cg$ (respectively). Once again the Master theorem will give the same result (up to constant multiples), which is also identical (up to constant multiples) to what we would get by solving the original recurrence only on powers of two.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9569