Si tengo la siguiente relación de recurrencia, $$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n $$ ¿Cómo podría demostrar que $T(n)\le cn\lg(n)+dn $ para algunos reales $c$ y $d$ ?
Respuesta
¿Demasiados anuncios?
Tenga en cuenta que $\lceil n/2 \rceil = \lfloor (n+1)/2\rfloor$ . De ello se desprende que
$$\begin{align*}T(n+1) - T(n) &= T(⌊(n+1)/2⌋)+T(\lceil (n+1)/2\rceil) - T(\lfloor n/2 \rfloor)- T(\lceil n/2\rceil) + 1\\ &= T(\lceil (n+1)/2\rceil) - T(\lfloor n/2 \rfloor) + 1\\ &= T(\lfloor n/2 \rfloor + 1) - T(\lfloor n/2 \rfloor) + 1 \end{align*}$$
Por lo tanto, $$\Delta T(n) = 1 + \Delta T(\lfloor n / 2 \rfloor)$$
donde $\Delta$ es el operador de diferencia hacia adelante . Reconocemos que esto se satisface con el número de bits necesarios para expresar $n$ en binario. Así,
$$\Delta T(n) = \lceil \lg (n + 1) \rceil$$
Así, $$T(n) = T(1) + \sum_{k=1}^{n-1} \lceil \lg (k + 1) \rceil = T(1) + \sum_{k=2}^{n} \lceil \lg k \rceil$$
Para resolver esta ecuación, dejemos que $m = \lceil \lg n \rceil$ . Entonces
$$\begin{align*} T(n) + (2^m - n) m &= T(1) + \sum_{k=2}^{2^m} \lceil \lg k \rceil \\ &= T(1) + \sum_{j=2}^m j2^{j-1} = T(1) + 2^m(m - 1) \end{align*}$$
Así, $$T(n) = n \lceil \lg n \rceil - \lceil \lg n \rceil + T(1)$$
Creo que puedes seguir desde aquí.
