# Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem

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?

-
Another take on the same results is the Akra-Bazzi theorem "On the Solution of Linear Recurrence Equations", Computational Optimization and Applications, 10(2), 195-210 (1998), or Drmota and Szpankowski "A Master Theorem for Discrete Divide and Conquer Recurrences", SODA'11 <dl.acm.org/citation.cfm?id=2133036.2133064>;. –  vonbrand Feb 7 '13 at 14:24
Here's a link to the above paper, which is not behind a paywall. –  Paresh Feb 7 '13 at 15:21
IIRC this is discussed in CLRS chapter 4. –  Kaveh Feb 8 '13 at 7:36
@Kaveh Thanks for the pointer. For the most part, they call it "tolerable sloppiness"; this is fine in their context, because they assume you only derive a hypothesis, later to be proven correct by induction. They mention the dangers (4.6). In 4.6.2 they give a proof, but it is high-level and they don't explicitly say what restrictions on $T$ have to be in place. So it seems to be something like "$T$ such that the maths go through", which I think mainly requires $f$ to have a "nice" $\Theta$-class. –  Raphael Feb 8 '13 at 10:34
In general case when you don't have similar sizes you can use Akra–Bazzi method which is generalization of master theorem, sure how to change specific function to something which works in this theorem needs a little trick, and for something like merge sort, this is what normally people are using to proof time complexity. –  user742 Feb 12 '13 at 13:29

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.

-
Finally got to read this more closely. Nice, thanks! I thought I'd note this for future readers (because I stumbled about it): $T(2^m) \in \Theta(T(2^{m+1}))$ is not a restriction since it is only false for super-polynomial $T$ and the Master theorem does not apply to such. –  Raphael Jun 23 '13 at 19:05
I have tried writing down your proof in more detail and got stuck proving your last sentence, "which is also identical (...) to what we would get by solving the original recurrence only on powers of two." In particular, we have to show that we end up in the same case of the Master theorem for $cg$, $f$ and $Cg$. This is no issue for cases 1 and 2, but I can't show the existence of $c < 1$ for case 3 (cf the version in CLRS, p94 in 3rd edition). Did you think about that, or did you work with a version similar to the Wikipedia one? –  Raphael Nov 25 '13 at 18:54
This is a technicality. If $f = \Theta(n^\alpha)$ then the problem goes away, see for example users.encs.concordia.ca/~chvatal/notes/master.pdf. The function $g$ will automatically satisfy the conditions. I imagine that the same thing works for $f = \Theta(n^\alpha \log^\beta n)$ and so on. Alternatively, just state this condition directly on $g$ rather than on $f$: there must exist some "regular" $g$ satisfying $f = \Theta(g)$. –  Yuval Filmus Nov 26 '13 at 1:58
Well, you claimed "$g$ monotone" was a sufficient condition (and I believed you) so I tried to work with that. The Master theorem as given in e.g. CLRS applies to e.g. $f : n \mapsto 2^n$, if I am not mistaken, so a restriction to polylogarithmic functions or somesuch is not "technical" but properly weakens the result. Lifting the "regularity" to $g$ does not help, by the way: I already have it in the crucial case via regularity of $cg$/$Cg$ (by assumption). So I'm back at my former comment, unfortunately. If this is really only technical, I don't see it. Too many inequalities. –  Raphael Nov 26 '13 at 2:15
I still think it's a technicality. The condition you're worried about is a technical condition. For most functions appearing in practice, the condition will hold. You're asking for the most general condition under which the proof sketch above goes through. That's an interesting question which I am too lazy to answer. –  Yuval Filmus Nov 26 '13 at 3:04