2
$\begingroup$

I was going the text Introduction to Algorithms by Cormen et al. Where I came across the following statement in the proof of the third case of the Master's Theorem.

(The Statement of Master theorem) Let $a \geqslant 1$ and $b > 1$ be constants, let $f(n)$ be a function, and let $T (n)$ be defined on the nonnegative integers by the recurrence( the recursion divides a problem of size $n$ into $a$ problems of size $n/b$ each and takes $f(n)$ for the divide and combine)

$T(n) = aT(n/b)+ f (n)$ ;

where we interpret $n/b$ to mean either $\lceil b/n \rceil$ or $\lfloor b/n \rfloor$. Then $T(n)$ has the following asymptotic bounds:

  1. If $f(n)=O (n^{\log_ba - \epsilon})$ for some constant $\epsilon > 0$, then $T(n)=\Theta (n^{\log_ba})$.

  2. If $f(n)=\Theta (n^{\log_ba})$, then $T(n)=\Theta (n^{\log_ba}\lg n)$

  3. If $f(n)=\Omega (n^{\log_ba + \epsilon})$ for some constant $\epsilon > 0$, and if $af(n/b) \leqslant cf(n)$ for some constant $c < 1$ and all sufficiently large n, then $T(n)=\Theta (f(n))$.

For $n$ as exact powers of $b$ we restrict the domain of T(n) as follows:

$$T(n)= \Theta(1), n=1$$ $$T(n)=aT(n/b)+f(n) ,n=b^i$$

Now in the proof of Master's Theorem with $n$ as exact power of $b$ the expression for $T(n)$ reduces to :

$$T(n)=\Theta(n^{\log_ba})+\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$

The recursion tree for the reduction of the recurrence to a summation

Then the authors assume the following,

$$g(n)=\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$

Then for the proof of the 3rd case of the Master's Theorem the authors prove the following lemma,

Lemma 1 : If $a\cdot f(n/b)\leqslant c\cdot f(n)$ for some constant $c<1$ and for all $n\geqslant b$ then $g(n)=\Theta(f(n))$

They say that:

under their assumption that $c<1$ and $n \geqslant b$,they have $a \cdot f(n/b)\leqslant c \cdot f(n) \implies f(n/b)\leqslant (c/a) \cdot f(n)$

then iterating $j$ times yields, $f(n/b^j)\leqslant (c/a)^j \cdot f(n)$

I could not quite get the mathematics used behind iterating $j$ times.

Moreover I could not quite get the logic behind the assumption of $n\geqslant b$ for the situation that $n$ should be sufficiently large. (As the third case of the Master's Theorem says.)

The proof of the lemma continues as follows:

$$f(n/b^j)\leqslant (c/a)^j\cdot f(n) \iff a^j\cdot f(n/b^j)\leqslant c^j\cdot f(n)$$ So, $$g(n)=\sum_{j=0}^{\log_bn -1} a^jf(n/b^j)$$ $$\leqslant \sum_{j=0}^{\log_bn -1} c^jf(n)$$ $$\leqslant f(n)\sum_{j=0}^{\infty} c^j,$$ as $c<1$ we have an infinite geometric series $$= f(n) \left(\frac{1}{1-c}\right)$$ $$=O(f(n))$$ as $c$ is a constant. (Note that $T(n)=\Omega(f(n))$ from the recursion diagram.)

Then the authors proof the third case of the Masters Theorem for $n$ as exact power of $b$:

Lemma 2: Let $a \geqslant 1$ and $b>1$, if $f(n)=\Omega (n^{\log_ba + \epsilon})$ for some constant $\epsilon > 0$, and if $af(n/b) \leqslant cf(n)$ for some constant $c < 1$ and all sufficiently large n, then $T(n)=\Theta (f(n))$.

So $$T(n) = \Theta(n^{\log_ba}) + g(n) = \Theta(n^{\log_ba}) + \Theta(f(n)) =\Theta(f(n))$$ as $f(n)=\Omega (n^{\log_ba + \epsilon})$

Moreover in the similar proof for the third case of the general master theorem (not assuming $n$ as exact powers of $b$) there again the book assumes that $n\geqslant b+b/(b-1)$ to go with the situation of sufficiently large $n$.

I do not quite understand what the specific value has to do and why such is assumed as sufficiently large $n$

(I did not give the details of the second situation as I feel that it shall be something similar to the first situation but however it can be found here)

$\endgroup$
2
$\begingroup$

Let's start with the issue of iteration. Suppose that a function $f$ satisfies $$ f(n/b) \leq (c/a)f(n). $$ Then it also satisfies $$ f(n/b^2) \leq (c/a)f(n/b) \leq (c/a)^2 f(n). $$ You can prove by induction that for all integer $t \geq 0$, $$ f(n/b^t) \leq (c/a)^t f(n). $$

As for your second question, about assuming that $n$ is large enough: the proof is just sloppy. You cannot assume that $f(n/b) \leq (c/a) f(n)$ holds for all $n \geq b$. Indeed, in Introduction to Algorithms, third edition, they do not make such an assumption for the case where $n$ is a power of $b$.

They do seem to make such as assumption in the case of general $n$, but what they are really saying is that the inequality $f(\lceil n/b \rceil) \leq (c/a) f(n)$ only makes sense for $n \ge b + b/(b-1)$. Using the idea of the proof of the special case where $n$ is a power of $b$, you can complete the proof of the general case. I would, however, strongly suggest ignoring such technicalities at present. The master theorem is essentially a calculation, and you can trust the authors that it works out. Nothing interesting is hidden under the rug.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @YuvalFimus I have modified the question with the details of the proof included, I could understand your explanation of the iteration part... Please can you help me out with the $n\geqslant b$ part as you said that answering it required more details... $\endgroup$ – Abhishek Ghosh Jun 20 at 6:23
  • 1
    $\begingroup$ This is of no help. Crucial context is missing. Their assumption doesn't imply that $f(n/b) \leq (c/a) f(n)$ for all $n \geq b$, and they must be saying something about this. $\endgroup$ – Yuval Filmus Jun 20 at 9:09
  • $\begingroup$ Nothing more is written about their assumption and implication. May be it was weird and that's why they dealt away with it in 3rd edition(as you pointed out). I thought that they might have got the assumption of $n\geq b+ \frac{b}{b-1}$ in same manner as they made the assumption for $n \geq b$. I was quite disturbed as I was unable to make out those two technicalities(which are sloppy and not quite clear). Thanks a lot for the help... $\endgroup$ – Abhishek Ghosh Jun 20 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.