0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – peterwhy
    Apr 27, 2016 at 13:22
  • $\begingroup$ 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. $\endgroup$
    – Clement C.
    Apr 27, 2016 at 13:29
  • $\begingroup$ And then $16^{\log n}$ can be simplified. $\endgroup$
    – peterwhy
    Apr 27, 2016 at 13:30

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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.) $\endgroup$
    – Clement C.
    Apr 27, 2016 at 13:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .