Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

4 Answers 4

up vote 2 down vote accepted

Hmm, possibly another way of heuristics is instructive.
First write the undisputable elements of the sequence:
$$\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.

share|improve this answer
    
Correct answer! –  hAu Dec 9 at 21:28

There is another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives $T(1)=1$) $$T(n) = 2 T(\lfloor n/2 \rfloor) + n^3.$$

Furthermore let the base two representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 2^k.$$

Then we can unroll the recurrence to obtain the following exact formula for $n\ge 1$ $$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j \left( \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j} \right)^3.$$

Now to get an upper bound consider a string of one digits which yields $$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j \left( \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j} \right)^3.$$

Note that this bound is attained and cannot be improved. It simplifies to $$\frac{32}{3} 8^{\lfloor \log_2 n \rfloor} - 24 \times 4^{\lfloor \log_2 n \rfloor} + \left(6 \lfloor \log_2 n \rfloor + \frac{40}{3}\right) \times 2^{\lfloor \log_2 n \rfloor} + 1.$$

The lower bound is for the case of a one digit followed by a string of zeros and yields $$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j \left( 2^{\lfloor \log_2 n \rfloor-j} \right)^3.$$ It simplifies to $$\frac{4}{3} 8^{\lfloor \log_2 n \rfloor} - \frac{1}{3} 2^{\lfloor \log_2 n \rfloor}$$ and this matches the results posted by the other contributors.

Joining the dominant terms of the upper and the lower bound we obtain the asymptotics $$2^{3 \lfloor \log_2 n \rfloor} \in \Theta\left(2^{3 \log_2 n}\right) = \Theta\left(n^3\right).$$

These are both in agreement with what the Master theorem would produce.

This MSE link has a series of similar calculations.

share|improve this answer

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

share|improve this answer
2  
+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
1  
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
2  
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)$.)

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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