2
$\begingroup$

Given the following recursion,
$$T(n)=T(\frac{n}{2})+ aT(\frac{n}{4})+n^2, $$ How can I find the minimal value for $a$ such that ${T(n)=ω(n^2)}$?

I tried to do it by tree recursion but I did not succeed to prove it by this method.

$\endgroup$
  • $\begingroup$ Look up the Akra-Bazzi theorem, a generalization of the master theorem. $\endgroup$ – Yuval Filmus Apr 7 '17 at 12:49
  • $\begingroup$ @YuvalFilmus Can you present a full solution for this example ? $\endgroup$ – Software_t Apr 7 '17 at 12:55
5
$\begingroup$

Suppose for simplicity that $n$ is a power of 2. Construct the tree corresponding to the recursion – each vertex is labelled by the current value of $n$, has three children, one of which is a leaf. We assume for now that the tree continues forever. Associate with each edge a weight, which is $1$, $a$, or $1$, depending on which term it corresponds to. The weight of a vertex is the product of all weights in the path from the root to the vertex.

Consider the generating series $$P(x) = \frac{1}{1-x-ax^2} = \sum_{m=0}^\infty (x+ax^2)^m.$$ The coefficient of $x^k$ in $P(x)$ is the total weight of vertices whose label is $n/2^k$. Therefore $\tilde T(n) = n^2 P(1/4)$, where the tilde denotes that there is no base case and the recursion continues forever (we will discuss this later on). Thus $\tilde T(n) = \omega(n^2)$ iff the power series $P(x)$ diverges at $x = 1/4$. This happens if $1/4 + a/4^2 \geq 1$, that is, if $a \geq 12$.

There is a slight problem with this argument, namely the tree doesn't continue forever. However, it is easy to see that all leaves are at depth $\Theta(\log n)$, or more accurately, at depths between $\log_4 n$ and $\log_2 n$ (assuming a base case $T(1) = 1$). This shows that $$ \sum_{m=0}^{\log_4 n} \left(\frac{1}{4}+\frac{a}{16}\right)^m \leq T(n) \leq \sum_{m=0}^{\log_2 n} \left(\frac{1}{4}+\frac{a}{16}\right)^m. $$ When $a < 12$, the preceding argument already shows that $T(n) = \Theta(n^2)$. When $a = 12$, these bounds show that $T(n) = \Theta(n^2 \log n)$. When $a > 12$ these bounds are not enough to determine the asymptotics, though definitely $T(n) = \omega(n^2)$.

The Akra–Bazzi method is a general form of this argument. To solve your recursion, you first have to find the value of $p$ such that $(1/2)^p + a(1/4)^p = 1$. Given that, the Akra–Bazzi theorem tells you that $$ T(n) = \Theta(n^p) \cdot \left(1 + \int_1^n \frac{u^2 \, du}{u^{p+1}}\right) = \begin{cases} \Theta(n^2) & p < 2, \\ \Theta(n^2\log n) & p = 2, \\ \Theta(n^p) & p > 2. \end{cases} $$ (I leave the case analysis needed to prove the formula on the right-hand side to you. It is very instructive.) The critical point is when $p = 2$, and this happens when $1/4 + a/16 = 1$, that is, when $a = 12$, and so in this case $T(n) = \Theta(n^2 \log n)$. When $a < 12$ we have $p < 2$, and so in this case $T(n) = \Theta(n^2)$. These results agree with the calculations above. Finally, when $a > 12$ we have $p > 2$, and so in this case $T(n) = \Theta(n^p)$, the estimate which was too difficult for our crude method above.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wow, can you explain more about the construction of the tree? I dont understand this part "each vertex is labelled by the current value of nn, has three children, one of which is a leaf" $\endgroup$ – Software_t Apr 7 '17 at 13:55
  • $\begingroup$ This is just the recursion tree. Intuitively, $T(n)$ has three children, $T(n/2)$ with weight 1, $T(n/4)$ with weight $a$, and a leaf $n^2$ with weight 1. $\endgroup$ – Yuval Filmus Apr 7 '17 at 14:07
  • $\begingroup$ can you explain how you constructed ${P(x)}$? Or bring me sources on this subject so that I can study this subject in a more profound way? $\endgroup$ – Software_t Apr 7 '17 at 14:56
  • $\begingroup$ There are many resources on generating functions, such as Wilf's Generatingfunctionology. $\endgroup$ – Yuval Filmus Apr 7 '17 at 14:59
  • $\begingroup$ I meant to the link between "generating functions" and "recursive tree". $\endgroup$ – Software_t Apr 7 '17 at 15:04
1
$\begingroup$

Let's make a guess that $T (n) = k·n^2$ for some k > 0. The recursion formula tells us that $T (n) = (k/4 + ak/16 + 1)·n^2$, so this works if $k = k/4 + ak/16 + 1$ or $(12 - a)·k = 16$. If a < 12 then we get the easy solution $k = 16 / (12 - a)$. If a ≥ 12 then there is no solution k > 0, so T (n) does not have the form $T (n) = k·n^2$.

You could then try to find $T (n)$ for $n = 2^m$, given a ≥ 12.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you see how can i find ${T(n)}$ for ${n=2^m}$ , given a≥12 ? $\endgroup$ – Software_t Apr 8 '17 at 18:30
  • $\begingroup$ @YuvalFilmus Can you help with this way? $\endgroup$ – Software_t Apr 8 '17 at 18:44

Not the answer you're looking for? Browse other questions tagged or ask your own question.