Hay otra estrechamente relacionada con la recurrencia que admite una exacta
solución. Supongamos que tenemos $T(0)=0$ $n\ge 1$ (esto le da
$T(1)=1$)
$$T(n) = 2 T(\lfloor n/4 \rfloor) + \lfloor \sqrt{n} \rfloor.$$
Además vamos a la base de cuatro representación de $n$ ser
$$n = \sum_{k=0}^{\lfloor \log_4 n \rfloor} d_k 4^k.$$
Entonces podemos desenrollar la recurrencia para obtener la siguiente exacta
fórmula para $n\ge 1$
$$T(n) = \sum_{j=0}^{\lfloor \log_4 n \rfloor}
2^j\Bigg\lfloor
\sqrt{\sum_{k=j}^{\lfloor \log_4 n \rfloor} d_k 4^{k-j}}
\Bigg\rfloor.$$
Ahora para obtener un límite superior considere una cadena de dígitos con valor de tres
para obtener
$$T(n) \le \sum_{j=0}^{\lfloor \log_4 n \rfloor}
2^j \sqrt{\sum_{k=j}^{\lfloor \log_4 n \rfloor} 3\times 4^{k-j}}
= \sum_{j=0}^{\lfloor \log_4 n \rfloor}
2^j \sqrt{4^{\lfloor \log_4 n \rfloor +1 - j} -1}
\\ < \sum_{j=0}^{\lfloor \log_4 n \rfloor}
2^j \sqrt{4^{\lfloor \log_4 n \rfloor +1 - j}}
= \sum_{j=0}^{\lfloor \log_4 n \rfloor}
\sqrt{4^{\lfloor \log_4 n \rfloor +1}}
\\ = (\lfloor \log_4 n \rfloor + 1) \times
2^{\lfloor \log_4 n \rfloor +1}.$$
Este bound es realmente alcanzado y no pueden ser mejorados, como
el límite inferior, que se produce con un dígito, seguido por ceros a
dar
$$T(n) \ge \sum_{j=0}^{\lfloor \log_4 n \rfloor}
2^j \sqrt{4^{\lfloor \log_4 n \rfloor-j}}
= \sum_{j=0}^{\lfloor \log_4 n \rfloor}
\sqrt{4^{\lfloor \log_4 n \rfloor}}
\\ = (\lfloor \log_4 n \rfloor + 1) \times
2^{\lfloor \log_4 n \rfloor}.$$
Unirse a la dominante en términos de la parte superior y el límite inferior obtenemos
el asymptotics
$$\lfloor \log_4 n \rfloor \times
2^{\lfloor \log_4 n \rfloor}
\en \Theta\left(\log_4 n \times 4^{1/2 \log_4 n}\right)
= \Theta\left(\log n \times \sqrt{n}\right).$$
Observar que no hay un orden menor plazo
$$2^{\lfloor \log_4 n \rfloor}
\en \Theta\left(4^{1/2 \log_4 n}\right)
= \Theta\left(\sqrt{n}\right).$$
Lo anterior es de acuerdo con lo que el Maestro teorema se iba a producir.
Anexo 3 De Noviembre De 2014. El límite inferior es la falta de un orden menor plazo,
que es $-(2^{\lfloor \log_4 n \rfloor+1}-1)$ el mismo que se ha hecho en este
MSE enlace.
Aquí es otro cálculo en el mismo espíritu:
MSE enlace.
