1
$\begingroup$

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)<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)<cf(n)$ 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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.