# Solve $T(n)=16T(n/2)+2n^4$

Solve using the iteration method:

$$T(n)=16T(n/2)+2n^4$$

My attempt:

\begin{align} T(n) &=16\cdot16T(n/2^2)+2(n/2)^4+2n^4 \\ &=16\cdot16\cdot 16T(n/2^3)+2(n/2^2)+2(n/2)^4+2n^4\\ &=16\cdot16\cdot 16\cdot 16 T(n/2^4)+2(n/2^3)^4+2(n/2^2)+2(n/2)^4+2n^4\\ &\vdots\\ &=16^kT(\frac{n}{2^k})+\sum_{k=1}^{k=i}2(\frac{n}{2^{i-1}})^4 \end{align}

stops when $\frac{n}{2^k}=1\Longrightarrow k=\log n$

$$T(n)=16^{\log {n}}T(1)+\sum_{\log n=1}^{\log n=i}2(n/2^{\log n-1})^4$$

What should I do now? is it correct? other solutions? thanks

• You accidentally replaced the $i$ inside the summation on the last line, and the fourth power is missing, and the $k$ and $i$ of the summation is mixed up. Apr 27, 2016 at 13:22
• I may be easier to first consider the case $n=2^k$, and deal with $T(2^k)$ (the general case, at least for asymptotics, will follow, and in any case this will give you a much simpler derivation for that case. Apr 27, 2016 at 13:29
• And then $16^{\log n}$ can be simplified. Apr 27, 2016 at 13:30

To gain intuition (and get the "right" solution), it is simpler to start consider the case where $n$ is a power of $2$, i.e. $n=2^k$ for some integer $k \geq 0$. (In what follows, all logarithms are in base $2$, because computer science.)
We can write \begin{align} T(2^k) &= 16 T(2^{k-1}) + 2\cdot 2^{4k} = 2^4 T(2^{k-1}) + 2^{4k+1} \\ &= 2^4 \left(2^4 T(2^{k-2}) + 2^{4(k-1)+1}\right) + 2^{4k+1} \\ &= 2^{2\cdot 4} T(2^{k-2}) + 2^{4k+1} + 2^{4k+1} = 2^{2\cdot 4} T(2^{k-2}) + 2\cdot 2^{4k+1}\\ &= 2^{3\cdot 4} T(2^{k-3}) + 3\cdot 2^{4k+1} \qquad\qquad\hfill\text{(Same substitution)}\\ &\vdots \\ &= 2^{\ell\cdot 4} T(2^{k-\ell}) + \ell\cdot 2^{4k+1} \\ &\vdots \\ &= 2^{k\cdot 4} T(2^{0}) + k\cdot 2^{4k+1} = 2^{4k} T(1) + 2k\cdot 2^{4k} \end{align} so that $T(2^k) = 2^{4k}\left( 2k+\alpha \right)$ for $\alpha\stackrel{\rm def}{=} T(1)$. In other terms, $$T(n) = n^4\left(2\log n + \alpha\right)$$ whenever $n$ is a power of two. Generalizing to general $n$ (I assume in this case the relation is missing $\lfloor\cdot\rfloor$ around the $\frac{n}{2}$) is standard, under the natural assumption that $T$ is non-decreasing.
As far as big-Oh notations are concerned, this leads to $$T(n) = \Theta( n^4\log n)$$ although we did obtain a tighter expression.
• Note that anyway the use of the case $n=2^k$ is implicit in what you did, since a priori given the context $T$ is only defined on integers. (Hence my comment about the missing floor around $n/2$ in the recurrence relation.) Apr 27, 2016 at 13:49