# Clarification of the proof involving the regularity condition in Master Theorem

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.

(Master theorem) Let $$a \geqslant 1$$ and $$b > 1$$ be constants, let $$f(n)$$ be a function, and let $$T (n)$$ be deﬁned 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 sufﬁciently large n, then $$T(n)=\Theta (f(n))$$.

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)$$

Let us assume,

$$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 that,

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

They say that as, $$a.f(n/b)\leqslant c.f(n) \implies f(n/b)\leqslant (c/a).f(n)$$ then interating $$j$$ times yeilds, $$f(n/b^j)\leqslant (c/a)^j.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).

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 satisfy 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)

Posted on Categories proxies