Costo total en una profundidad de i para $T(n) = 4T(n/2 + 2) + n$

Question

¿Cuál es el costo total en una profundidad de i para la relación de recurrencia $T(n) = 4T(n/2 + 2) + n$? Entiendo que en una profundidad de i, el número de nodos es $4^i$. Sin el término $ + 2 $, el costo total en una profundidad i sería $4^i * n/2^i$, pero el $+2$ complica esto considerablemente.

La parte superior del árbol tendría un costo de $n$, el siguiente nivel tendría un costo de $n/2 + 2$, el siguiente $(n/2 + 2)/2 + 2$, el siguiente $((n/2+2)/2+2)/2 + 2$. ¿Cómo sería el nivel i-ésimo?

Answer 1

Seguiré tu definición de costo.

Comienza con el nivel que tiene un costo $\frac{n}{2} + 2$ y llámalo el nivel $1$.

Observa que el nivel $i$-ésimo tendrá el siguiente costo:

$\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)$

Pon $i = 1, 2, 3, 4, \ldots$ ¡y verifica!

Answer 2

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}

Luego, el nivel $i$-ésimo de $F$ tiene peso $2^{i-1}n + 4^i$

Por lo tanto, los primeros $k$ niveles de $F$ tienen un peso total de $(2^{k}-1)n+(4^{k+1}-4)/3$

Así que los primeros $k$ niveles de $T$ tienen un peso total de $(2^{k}-1)(n-4)+(4^{k+1}-4)/3$