# Relaxing hypotheses of Master Theorem

This question is related to Master Theorem on oscillating function.

Consider a recurrence of the form

$$T(n) = a T(n/b) + f(n)$$

Master Theorem's regularity condition excludes some cases (for example, when $$f(n)$$ is oscillating).

Suppose, however, that $$f(n)=\Theta(g(n))$$ for a function $$g(n)$$ that does not violate the regularity condition, so that the Master Theorem is applicable if $$g(n)$$ is used instead of $$f(n)$$. Consider then the following recurrence:

$$T'(n) = a T'(n/b) + g(n)$$

and assume that the master theorem gives the solution $$T'(n)=\Theta(g(n))$$.

Can I then safely conclude that $$T(n)=\Theta(g(n))$$? Or there are some reasonable conditions on $$g(n)$$ we can add (I suppose that if $$g(n)$$ is polinomially bounded then maybe Akra-Bazzi method will apply, even if one have to swich integration and $$\Theta$$, and I'm not sure this is sound)?

Notice that from $$f(n)=\Theta(g(n))$$ we cannot deduce that $$f(n)$$ is always less than or equal to $$g(n)$$ or to a $$d\cdot g(n)$$ for some fixed $$d$$ (indeed, $$g(n)$$ can be equal to 0 for some value of $$n$$, so I'm not totally convinced by the answer to Regularity condition in the master Theorem in the presence of Landau notation for f as it is not possible to prove the base case of the induction, unless one changes the initial condition). So I cannot prove by induction that $$T(n) for all $$n$$ and, anyway, I only want to prove $$T(n)=\Theta(T'(n))$$.

To give some context, this is the case I want to apply the result to: consider the recurrence

$$T(n)=2\cdot T(n/2)+f(n)$$

where I only know that $$f(n)=\Theta(n\sqrt{n})$$. Then I can unfold the recurrence obtaining $$\begin{equation*} \begin{split} T&(n)=2T\left(\frac{n}{2}\right)+\Theta(n\sqrt{n})= 2\left(2T\left(\frac{n}{4}\right)+\Theta\left(\frac{n}{2}\sqrt{\frac{n}{2}}\right)\right)+\Theta(n\sqrt{n}) =\\ &=\ldots=2\left(2\left(2\ldots \left(2T\left(\frac{n}{2^h}\right)+\Theta\left(\frac{n}{2^{h-1}}\sqrt{\frac{n}{2^{h-1}}}\right)\right)\ldots\right)\right)+\Theta(n\sqrt{n}) \end{split} \end{equation*}$$

until $$2^h=n$$, i.e. $$h=\log(n)$$. Then $$T(n)=\sum_{i=0}^{\log(n)-1} 2^i\cdot\Theta\left(\frac{n}{2^i}\sqrt{\frac{n}{2^i}}\right)$$.

Performing the calculations I get $$\begin{equation*} \begin{split} T(n)&=\sum_{i=0}^{\log(n)-1} 2^i\cdot\Theta\left(\frac{n}{2^i}\sqrt{\frac{n}{2^i}}\right)=\Theta\left(\sum_{i=0}^{\log(n)-1} 2^i\cdot\frac{n}{2^i}\sqrt{\frac{n}{2^i}}\right)=\\ &=\Theta\left(n\sqrt{n}\cdot\sum_{i=0}^{\log(n)-1} \frac{1}{\sqrt{2^i}}\right) \end{split} \end{equation*}$$ The series $$\sum_{i=0}^{+\infty} \frac{1}{\sqrt{2^i}}$$ is convergent, so I can conclude (I hope correctly) that $$T(n)=\Theta(n\sqrt{n})$$.

On the other hand, I cannot directly apply Master Theorem, as from $$f(n)=\Theta(n\sqrt{n})$$ I cannot conclude $$2f\left(\frac{n}{2}\right) for some $$c<1$$. Indeed, if definitively we have $$c_1 n\sqrt{n}\leq f(n)\leq c_2 n\sqrt{n}$$, then

$$f(n)\geq c_1 n\sqrt{n}= 2\sqrt{2}c_1 \frac{n}{2}\sqrt{\frac{n}{2}}\geq\frac{2\sqrt{2}c_1}{c_2} f\left(\frac{n}{2}\right)=\frac{\sqrt{2}c_1}{c_2} 2f\left(\frac{n}{2}\right)$$

and so

$$2f\left(\frac{n}{2}\right)\leq \frac{c_2}{\sqrt{2}c_1} f(n)$$

but $$\frac{c_2}{\sqrt{2}c_1}$$ is not necessarily less than 1.

## 1 Answer

Yes. Here is the idea.

If $$f(n) = \Theta(g(n))$$ then there exist constants $$C_1,C_2>0$$ such that for large $$n$$, $$C_1g(n) \leq f(n) \leq C_2g(n).$$ Now consider the two recurrences $$T_1(n) = aT_1(n/b) + C_1g(n) \\ T_2(n) = aT_2(n/b) + C_2g(n)$$ Choosing suitable initial conditions, you can prove inductively that $$T_1(n) \leq T(n) \leq T_2(n).$$ You consider a regime in which applying the master theorem gives you that $$T_1(n) = \Theta(g(n))$$ and $$T_2(n) = \Theta(g(n))$$. It follows that $$T(n) = \Theta(g(n))$$.