# Recurrence trouble: $T(n)=2T(n/2)+T(n/3)+\theta(n^2)$

I have to solve the following recurrence :$\displaystyle T(n)=2T(n/2)+T(n/3)+\theta(n^2)$

I have done the whole tree analyses and now I have to prove that $\displaystyle T(n) \leq dn^{2}\log_{2}(n)$ but I can not find mathematical way to prove that, is there any trick with logarithms that I can use?

-
What does θ mean? Is it a typo (T(n^2))? –  Américo Tavares Nov 15 '10 at 12:43
Θ is Big Theta notation but we can just say T(n)=2*T(n/2)+T(n/3)+n^2 –  ECE Nov 15 '10 at 12:48
Please excuse me, and what is d? –  Américo Tavares Nov 15 '10 at 12:53
it is a constant –  ECE Nov 15 '10 at 13:11
What are tree analyses? –  Peter Shor Nov 15 '10 at 22:46

Try applying the Akra-Bazzi theorem.

By Akra-Bazzi, if $p$ satisfies

$\displaystyle 2(1/2)^p + (1/3)^p = 1$, (notice that $\displaystyle 1 \lt p \lt 2$)

then

$\displaystyle T(x) = \theta(x^p(1 + \int_{1}^{x} x^{1-p})) = \theta(x^p(1+x^{2-p}))$

since $\displaystyle 1 \lt p \lt 2$

we must have that

$\displaystyle T(x) = \theta(x^2) = O(x^2 \log_{2} x)$.

-
I tried to say the following i have a cost per try layer which is (11/18)^k*cn where k is the layer –  ECE Nov 15 '10 at 14:10
@ECE: What? I don't understand. –  Aryabhata Nov 15 '10 at 14:16
I tried to say the following i have a cost per tree layer which is (11/18)^kcn^2 where k is the layer so i can sum and find cost, so "cost" is sum from i=0 to log2(n-1) of (11/18)^icn^2 plus Θ(n^log2(3)) where theta declares cost at leafs but then i get a difficult to simplify equation so i say that my cost is smaller than sum from i=0 to inf of (11/18)^i*cn^2 plus Θ(n^log2(3)) and then i get Ο(n^2) but i think that there is an other better method to find a smaller O,Ω –  ECE Nov 15 '10 at 14:17
@ECE: I still have no clue what you are trying to say. I have edited the answer to add more information. –  Aryabhata Nov 15 '10 at 14:39
I analyzed my Recurrence using recursion tree an i found tree_height=log2(n) and cost_per_layer=((11/18)^k)*cn^2 so i now can say T(n)= sum from i=0 to log2(n-1) of((11/18)^i)*cn^2 +Θ(n^lg2(3)) theta is for leafs and then i calculated sum and i got an equation (((11/18)^log2(n)-1)/(11/18-1))*cn^2 +Θ(n^lg2(3)) but this expression is too complex so i said that T(n)<=sum from i=0 to inf of (11/18)^i*cn^2 plus Θ(n^log2(3)) and then i found that my equation is asymptotically equal to O(n^2).but i don't know i think there should be a better way calculating theta for this Recurrence –  ECE Nov 15 '10 at 14:46

Do it by induction. First, let's set the constant in $\theta$ to 1, so we get

$T(n)=2T(n/2)+T(n/3)+n^2$

Now, assume $T(m) \leq k m^2$ for some constant $k$ for all $m < n$. Then

$T(n) = 2 T(n/2) + T(n/3) + n^2 \leq k n^2/2 + k n^2/9 + n^2 \leq (11 k /18 +1) n^2$

and if $k = 3$, say, we have

$T(n) \leq (11/6+1) n^2 \leq 3 n^2.$

so if our bound holds for all $m < n$, then our bound holds for $n$.

To make this a real proof, you would need to take the case when $n$ is not a multiple of 6 into account, but the details will work out when you do them carefully.

-

For suitable constant $c$, $f(n) = (T(n)/n^2) + c$ satisfies a recurrence $f(n) = Af(n/2)+Bf(n/3)$ which has solutions (for continuous-valued $n$) of the form $n^\alpha$. This should give a guess about the asymptotics for integer $n$ and one could probably incorporate lower order terms (fluctuations from the complex solutions with real part less than that of $\alpha$) by analyzing the zeros of $G(x)=1 - Ax^{\log 2} - Bx^{\log 3}$ or the generating function with real exponents (generalized power series expansion) for $1/G(x)$.

I think this type of exercise for the large $n$ asymptotics and translation to the continuous problem is in books such as (e.g.) Flajolet and Sedgewick's text on asymptotic combinatorics. However, for this specific recurrence it might be possible to go beyond the standard asymptotics and handle integer-valued $n$ directly, because the operations of replacing $n$ by $P(n)=[n/2]$ and $Q(n)=[n/3]$ commute. One could look at base 6 expansions of $n$, or classify integers according to which operations $P^a Q^b$ take them to $0$ and $1$, and sums over the $(a,b)$ would give an integer-valued expansion formula for $f(n)$, similar to the binomial theorem or the expansion of a rational generating function $1/(1-H(x))$ as a geometric series.

-