7
$\begingroup$

I am asking for references regarding a special case of the master theorem. This theorem seems to appear quite a lot on this site, prompting me to study it in more detail, e.g. see my posts here and here. It seems to me that it has some special cases which I will present to you that can be treated in a very simple way and without involving complicated machinery. This special case is the one where the cost at the recursion step is $n$ and the subproblems are obtained by dividing $n$ by powers of a single unique prime.

For example, take $T(0) = 0$ and consider the recurrence (the prime being two) $$T(n) = T(n/2) + 3 T(n/4) +n.$$

Let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ be the binary representation of $n.$

It is not difficult to see that $$ T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} [z^j] \frac{1}{1-\frac{1}{2} z -\frac{3}{4} z^2} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k \tag{1}.$$ This formula is exact for all $n.$

Now we have $$[z^j] \frac{1}{1-\frac{1}{2} z -\frac{3}{4} z^2} = \frac{2}{\sqrt 13} \left( \left(\frac{1+\sqrt{13}}{4}\right)^{j+1} - \left(\frac{1-\sqrt {13}}{4}\right)^{j+1} \right) = \frac{2}{\sqrt{13}} \left(\rho_1^{j+1} - \rho_2^{j+1} \right), $$ where we have introduced $$\rho_{1,2} = \frac{1\pm\sqrt{13}}{4}.$$

To get a lower bound on $T(n)$, consider the case of a single one followed by zeros, giving $$ T(n) \ge \frac{2}{\sqrt{13}} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\rho_1^{j+1} - \rho_2^{j+1} \right) 2^{\lfloor \log_2 n \rfloor} = \frac{2^{\lfloor \log_2 n \rfloor+1}}{\sqrt{13}} \left( \frac{\rho_1^{\lfloor \log_2 n \rfloor+2}-1}{\rho_1-1} - \frac{\rho_2^{\lfloor \log_2 n \rfloor+2}-1}{\rho_2-1} \right) .$$ This bound is actually attained.

For an upper bound, consider the case of a string of ones, $$ T(n) \le \frac{2}{\sqrt{13}} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\rho_1^{j+1} - \rho_2^{j+1} \right) \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k = \frac{2}{\sqrt{13}} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\rho_1^{j+1} - \rho_2^{j+1} \right) \left(2^{\lfloor \log_2 n \rfloor+1}-2^j\right) \\ = \frac{2^{\lfloor \log_2 n \rfloor+2}}{\sqrt{13}} \left( \frac{\rho_1^{\lfloor \log_2 n \rfloor+2}-1}{\rho_1-1} - \frac{\rho_2^{\lfloor \log_2 n \rfloor+2}-1}{\rho_2-1} \right) -\frac{1}{\sqrt{13}} \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left((2\rho_1)^{j+1} - (2\rho_2)^{j+1} \right).$$ The right term is $$-\frac{1}{\sqrt{13}} \left( \frac{(2\rho_1)^{\lfloor \log_2 n \rfloor+2}-1}{2\rho_1-1} - \frac{(2\rho_2)^{\lfloor \log_2 n \rfloor+2}-1}{2\rho_2-1} \right).$$ This bound too is attained. The spread between upper and lower is a factor of $$ 2-2\frac{\rho_1-1}{2\rho_1-1}. $$

Taking these bounds together, we have shown that $$ T(n) \in \Theta \left( (2\rho_1)^{\lfloor \log_2 n \rfloor} \right) = \Theta \left( n 2^{\log_2 \rho_1 \log_2 n} \right) = \Theta \left( n \times n^{\log_2 \rho_1} \right) = \Theta \left(n^{1+\log_2 \rho_1} \right).$$ This trick generalizes to the case where the subproblem reductions are not powers of a unique prime which I leave to the reader. I would be happy to see references for the technique I have presented here. I am essentially asking whether it is new or not. From what I have seen the exact value of the exponent in the exponential is usually left untreated, whereas I have shown above that it can be made exact. Would you say that my use of a generating function to encapsulate the mechanics of the problem size reduction in the recurrence is new?

Here is another MSE computation that uses the same method.

$\endgroup$
  • $\begingroup$ It should be obvious that the above also works for cost functions of the form $\log^p n \times n^q$ with $p$ and $q$ positive integers. $\endgroup$ – Marko Riedel Mar 5 '13 at 1:19
  • $\begingroup$ From what I have seen the exact value of the exponent in the exponential is usually left untreated... This seems not to be the case at all (or maybe I do not understand what you mean by "the exact value of the exponent in the exponential"). Would you say that my use of a generating function to encapsulate the mechanics of the problem size reduction in the recurrence is new?... No I would not. $\endgroup$ – Did Jun 21 '13 at 11:50
  • $\begingroup$ Got something from an answer below? $\endgroup$ – Did Jun 29 '13 at 20:19
2
$\begingroup$

A hands-on approach is to find some hereditary upper and lower bounds of $T(n)$ by multiples of powers of $n$.

If $T(n)=T(n/2)+3T(n/4)+n$, one first centers the recursion using $S(n)=T(n)+cn$, then $$ S(n)=S(n/2)-cn/2+3T(n/4)-3cn/4+n+cn=S(n/2)+3S(n/4), $$ if $c=4$. From now on, $S(n)=T(n)+4n$.

Thus, the centering step is based on the affine part of the recursion, here $+n$.

Second, assume that $S(k)\bowtie c k^a$ for $k=n/2$ and $k=3n/4$ with $a\gt1$, where $\bowtie$ is either $\leqslant$ or $\geqslant$. Then $S(n)\bowtie cn^a/2^a+c3n^a/4^a=(1/2^a+3/4^a)cn^a$. From now on, assume that $a$ solves $$ \frac1{2^a}+\frac3{4^a}=1. $$ Then the property $S(n)\bowtie cn^a$ is hereditary for every fixed $c$.

Thus, the power step is based on the linear part of the recursion, here $T(n/2)+3T(n/4)$.

In particular, for some small enough $c$ and some large enough $C$, it holds that $$ cn^a-4n\leqslant T(n)\leqslant Cn^a-4n, $$ for every $n$. Since $a\gt1$ in the present case, the contribution of the linear part of the recursion wins hence all this is more than enough to prove that $$ T(n)=\Theta(n^a). $$ One thing is clear though, which is that the fact that $1/2$ and $1/4$ are inverses of powers of a unique prime, invoked in the OP, does not enter the picture. Nevertheless, to relate $a$ to the exponent $\rho_1$ in the OP, assume that $a=1+\log_2\rho$, then $$ \frac1{2^a}+\frac3{4^a}=\frac1{2\rho}+\frac3{4\rho^2}, $$ hence $\rho$ solves $4\rho^2=2\rho+3$, that is, $\rho=\frac14(1\pm\sqrt{13})$, as claimed in the OP.

Edit: About the paragraph justifying the bounty, I would check the obvious references, namely generatingfunctionology and Flajolet's books.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Good answer. The fact that the problem size reduction factors are inverse powers of a unique prime is what makes the exact formula possible. That is the special trick that makes the calculation go through. Actually it does not have to be prime, it just has to be unique. I do think it is nice to have exact upper and lower bounds. I am sure you can follow my above argument from the OP. $\endgroup$ – Marko Riedel Mar 5 '13 at 17:47
  • $\begingroup$ The fact that the problem size reduction factors are inverse powers of a unique prime is what makes the exact formula possible. Sorry but I fail to see what you mean by that. $\endgroup$ – Did Jun 21 '13 at 11:54
  • 1
    $\begingroup$ @Did I think the OP means that the fact that $\frac{1}{2^a}+\frac{3}{4^a}=1$ has an 'elementary' solution (one in which $a$ can be written as the logarithm to some base of an algebraic number) is a consequence of $4^a$ being a power of $2^a$ so that the whole equation is polynomial in $2^{-a}$. $\endgroup$ – Steven Stadnicki Jul 22 '13 at 6:42
  • $\begingroup$ @StevenStadnicki And this is mostly irrelevant, as explained in my answer. $\endgroup$ – Did Feb 8 '15 at 18:11
1
$\begingroup$

Look at the Akra-Bazzi theorem, it gives bounds for recurrences like yours. The proof is a blizzard of integrals...

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. I am aware of this theorem. I am looking for a reference for the exact formula that I give for $T(n)$ including the generating function. The reason I posted is precisely that my trick is very simple and works without using integrals, and as a bonus giving an exact rather than approximate result. Did you notice that the exponent in the final asymptotic bound is exact, too? $\endgroup$ – Marko Riedel Mar 5 '13 at 17:18

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.