5
$\begingroup$

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?

  • 0
    What does θ mean? Is it a typo (T(n^2))?2010-11-15
  • 0
    Θ is Big Theta notation but we can just say T(n)=2*T(n/2)+T(n/3)+n^22010-11-15
  • 1
    Please excuse me, and what is d?2010-11-15
  • 0
    it is a constant2010-11-15
  • 0
    Hi @ECE, I don't think that bound is correct. Even at the first level, you are doing θ(n^2) work, so how can you bound the entire recurrence with O(n lg n)?2010-11-15
  • 0
    not O(nlgn) but O(n^2*lgn)2010-11-15
  • 0
    Ah I see. Anyone with edit rights that can come through and tex-ify the math?2010-11-15
  • 1
    What are tree analyses?2010-11-15

3 Answers 3

5

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

  • 0
    I tried to say the following i have a cost per try layer which is (11/18)^k*cn where k is the layer2010-11-15
  • 0
    @ECE: What? I don't understand.2010-11-15
  • 0
    I tried to say the following i have a cost per tree layer which is (11/18)^k*cn^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)^i*cn^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,Ω2010-11-15
  • 0
    @ECE: I still have no clue what you are trying to say. I have edited the answer to add more information.2010-11-15
  • 0
    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 Recurrence2010-11-15
  • 0
    @ECE: A better way is Akra-Bazzi as I just described! If this is homework and you are expecting a simpler answer, please say so.2010-11-15
  • 0
    on i have no limitation in answering something specific but i just wanted to know if a there is a "better result"2010-11-15
  • 0
    @ECE: What do you mean by better result? Akra-Bazzi immediately shows that T(n) = theta(n^2). What more are you expecting?2010-11-15
4

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.

1

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.