$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer, need help, I dont know how to solve it?
$T(1) = 1 , T(n) = 2T(n/2) + n^3$? Divide and conquer
-
0T(n)=O*T(n/2) + g(h) this is the method!! – 2011-03-08
4 Answers
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.
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). $
-
0@MIchael: Agree to that. – 2011-03-08
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)$.)
-
0I need one using the method that Im using – 2011-03-08
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.
-
0Correct answer! – 2014-12-09