Total cost at a depth of i for $T(n) = 4T(n/2 + 2) + n$

Question

What is the total cost at a depth of i for the recurrence relation $T(n) = 4T(n/2 + 2) + n$? I understand that at a depth of i, the number of nodes is $4^i$. Without the $ + 2 $ term the total cost at a depth i would be $4^i * n/2^i$, but the $+2$ complicates this considerably.

The top of the tree would have cost $n$, the next level would have cost $n/2 + 2$, the next $(n/2 + 2)/2 + 2$, the next $((n/2+2)/2+2)/2 + 2$. What would the ith level look like?

Answer 1

Consider \begin{align} F(n) &= T(n+4) \\ &= 4T\bigg(\frac{n+4}{2} + 4\bigg) + (n+4)\\ &= 4F\bigg(\frac{n}{2}\bigg) + (n+4) \end{align}

Then the $i$'th level of $F$ has weight $2^{i-1}n + 4^i$

So the first $k$ levels of $F$ have total weight $(2^{k}-1)n+(4^{k+1}-4)/3$

So the first $k$ levels of $T$ have total weight $(2^{k}-1)(n-4)+(4^{k+1}-4)/3$

Answer 2

I'll follow your definition of cost.

Start with the level having cost $\frac{n}{2} + 2$ and call it the $1$st level.

Observe that the $i$-th level will have the following cost:

$\displaystyle \frac{n}{2^i} + \frac{1}{2^i} \sum_{k=1}^i 2^{k+1}$

$= \frac{n}{2^i} + \frac{4}{2^i} \left(2^i - 1 \right)$

Put $i = 1, 2, 3, 4, \ldots$ and verify!