# $T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer

$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer, need help, I dont know how to solve it?

-
i've got: (2^3)*T(n/(2^3)) + (2^2)*(n/(2^2))^3 + 2(n/2)^3 + n^3 should my GUESS be: (2^k)*T(n/(2^k)) + (n^3)( 1 + (2^(k-1) )*( 1/( 2^(k-1) ))^3 ) ????, please I need someone to divide and conquer this!! –  hAu Mar 8 '11 at 0:00
the big issue is that i need to EXPAND then GUESS a posible equation then get rid of T(n/2) and then find a solution that T(1)=1; I already know that the solution is n^3+2∗((n+1)/3), but I need to see the WHOLe thing by EXPANDING, THANK YOU EVERYBODY!!! –  hAu Mar 8 '11 at 6:48
T(n)=O*T(n/2) + g(h) this is the method!! –  hAu Mar 8 '11 at 6:54

The homogeneous part of the equation $T(n) =2 T(n/2)$ has the general solution $$T_0(n) = C n.$$ So all what we have to do is find a particular solution of the inhomogeneous equation $$T(n) = 2 T(n/2) + n^{3} .$$ Quite often it is good to try an ansatz which has the same form as the inhomogeneous term. Therefore, we try $T_p(n) = c n^3$ which yields $$c n^3 = \frac{c}{4} n^3 + n^3.$$ Solving for $c$, we get the particular solution $T_p(n)= \frac{4}{3} n^3$.

The general solution therefore has the form $T(n) =T_0(n) + T_p(n)$. With the initial condition $T(1)=1$, we obtain $C= - \frac{1}{3}$. So the solution is given by $$T(n) = \frac{n}{3} (4 n^2 -1).$$

-
+1: Just a note: Usually n is only allowed to be a positive integer... I say this because OP talks about divide and conquer. And even though OP didn't actually specify T(n/2) correctly, this is an abuse of notation prevalent in algorithm complexity analysis. –  Aryabhata Mar 7 '11 at 23:30
I would say $n$ is only allowed to by $2^k$ for $k\in \mathbb{N}$. That's also the spirit in which one should read my answer (for other $n$ one should first think hard what it actually means). –  Fabian Mar 7 '11 at 23:35
Usually $T(n/2)$ is "short" for $T(\lfloor n/2 \rfloor)$. In some sense it is valid, as that is how integer division is defined, i.e. in most programming languages, if you try dividing a positive integer $n$ by $2$, you get $\lfloor n/2 \rfloor$. –  Aryabhata Mar 7 '11 at 23:45
It's also possible that $2T(n/2)$ is short'' for $T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil)$ -- that is, to solve a problem of size $n$ we break it up into two subproblems of size as close to equal as possible, and it takes time $n^3$ to put those answers together. Of course one generally ignores the floors and ceilings when thinking about asymptotics. –  Michael Lugo Mar 8 '11 at 0:50
@MIchael: Agree to that. –  Aryabhata Mar 8 '11 at 1:18

Use Akra-Bazzi which is more useful than the Master Theorem.

Using Akra-Bazzi, I believe you get $$T(x) = \theta(x^3)$$

You can also use the Case 3 of Master theorem in the wiki link above. (Note: That also gives $\theta(x^3)$.)

-
i've got: (2^3)*T(n/(2^3)) + (2^2)*(n/(2^2))^3 + 2(n/2)^3 + n^3 should my GUESS be: –  hAu Mar 7 '11 at 23:14
@hAu: I don't understand. Did you try reading the links about Master theorem and Akra-Bazzi? –  Aryabhata Mar 7 '11 at 23:18
Nice! I did not know about these theorems. I thought the question is about the solution of the recurrence equation and not only about the asymptotics... –  Fabian Mar 7 '11 at 23:24
i've got: (2^3)*T(n/(2^3)) + (2^2)*(n/(2^2))^3 + 2(n/2)^3 + n^3 should my GUESS be: (2^k)*T(n/(2^k)) + (n^3)( 1 + (2^(k-1) )*( 1/( 2^(k-1) ))^3 ) ???? –  hAu Mar 7 '11 at 23:29
@hau: If you want to solve it, you have to get rid of the $T$. It will be of the form $T(n) = \text{something}$ where $\text{something}$ does not contain $T$. –  Aryabhata Mar 7 '11 at 23:32
$$\begin{array} & a(1) &=&a(2^0) & = & 1 \\\ a(2)&=&a(2^1) &=&10 &= & 2^3 + 2*1 &=& 2*(4^1+1) \\\ a(4)&=&a(2^2) &=&84 &=& 4^3 + 2*10 &=& 4*(4^2+4^1+1) \\\ a(8)&=&a(2^3) &=&680 &=& 8^3 + 2*84 &=& 8^3+2*4^3+4*2^3+8*1^3\\\ & & & & &=& 8*(4^3+4^2+4^1+1) \\\ \ldots &=&a(2^k)&=& \ldots \end{array}$$ It is obvious how this can be continued, because at the exponent k we get always $8^k$ plus two times the previous, thus the weighted sum of all powers of 8 which can be expressed as consecutive powers of 4: $$a(2^k) = 2^k*(4^k+4^{k-1} \ldots +4^0)= 2^k*\frac{4^{k+1}-1}{4-1}$$ Now the step "divide" can be taken: the above gives also a meaningful possibility for interpolation of the non-explicitely defined elements. If we allow base-2 logarithms for k we get for
$$\begin{array} & & a(2^k) &= & 2^k*\frac{4^{k+1}-1}{4-1} \\\ & &= & 2^k*\frac{4*(2^{k})^2-1}{3} \\\ \text{assuming }& k&=& \frac{\log(n)}{\log(2)} \\\ & a(n) &=& n*\frac{4*n^2-1}{3} \\\ & &=& n^3 + \frac{(n-1)n(n+1)}{3!} \\\ & &=& n^3 + 2*\binom{n+1}{3} \\\ \end{array}$$ where the expression in the fourth line is the same as Fabian's result.