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:

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

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

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)