Recurrence which cannot be analyzed by master theorem [duplicate]

Question

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.

Answer 1

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.

Answer 2

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.