Question

Solve recurrence relation by repeated substitution (equation in comments)

Answer 1

\[T(n)=2T(\frac{ n }{2 })+n ^{3}\]

Answer 2

Successive iterations of the recurrence yield\[\begin{align*}
T(n)&=2T\left(\frac{n}{2}\right)+n^3\\[1ex]
&=2\left(2T\left(\frac{n}{4}\right)+\left(\frac{n}{2}\right)^3\right)+n^3\\[1ex]
&=2^2T\left(\frac{n}{2^2}\right)+\frac{2^2+1}{2^2}n^3\\[1ex]
&=2^2\left(2T\left(\frac{n}{2^3}\right)+\left(\frac{n}{2^2}\right)^3\right)+\frac{2^2+1}{2^2}n^3\\[1ex]
&=2^3T\left(\frac{n}{2^3}\right)+\frac{2^4+2^2+1}{2^4}n^3\\[1ex]
&~~\vdots\\[1ex]
&=2^kT\left(\frac{n}{2^k}\right)+\frac{2^{2(k-1)}+2^{2(k-2)}+\cdots+2^2+2^0}{2^{2(k-1)}}n^3\\[1ex]
&=2^kT\left(\frac{n}{2^k}\right)+2^{-2(k-1)}n^3\sum_{i=0}^{k-1}2^{2i}\\[1ex]
&=2^kT\left(\frac{n}{2^k}\right)+\frac{2^{2k}-1}{3\times2^{2(k-1)}}n^3
\end{align*}\]where the last simplification comes from
\[\sum_{i=0}^{k-1}r^i=\frac{r^k-1}{r-1}\]
Assuming you have an initial condition \(T(1)=C\), you need to rewrite the above general form in terms of \(T(1)\). This occurs when \(\dfrac{n}{2^k}=1\), or \(k=\log_2n\).
\[T(n)=2^{\log_2n}\underbrace{T\left(\frac{n}{2^{\log_2n}}\right)}_{C}+\frac{2^{2\log_2n}-1}{3\times2^{2(\log_2n-1)}}n^3=\cdots\]

Answer 3

@HolsterEmission thanks so much, I didn't think anyone on here could solve this.