Resolución de la relación de recurrencia

Quiero demostrar que la complejidad temporal de un algoritmo es poliglogarítmica en la escala de entrada.

La relación de recurrencia de este algoritmo es , donde .$T(2n) \leq T(n) + T(n^a)$$a\in(0,1)$

Parece que para algunos depende de . Pero no puedo probar esta desigualdad. ¿Cómo resolver esta relación de recurrencia?$T(n) \leq \log^{\beta}{n}$$\beta$$a$

Solo quiero obtener un pollogarítmico de límite superior en n.

Tu suposición está mal. De hecho, no es difícil demostrar que asumir$T(n) > 0$ para todos $n > 0$, entonces $T(n) = \Omega(\log^k n)$para todos $k$. De hecho, para que esto suceda, necesitamos eso lo suficientemente grande$n$ nosotros tendriamos

$$(1+a^k) \log^k n = \log^k n + \log^k n^a \geq \log^k (2n),$$ o $\sqrt[k]{1+a^k} \log n \geq \log n + \log 2$, que se mantiene siempre $[\sqrt[k]{1+a^k}-1]\log n \geq \log 2$, y en particular para lo suficientemente grande $n$.

¿Cuál es el orden correcto de crecimiento de $T(n)$? Para intentar averiguarlo, escribe$S(n) = T(2^n)$. La recurrencia ahora se convierte en

$$S(n+1) = S(n) + S(an).$$ Para grande $n$, esperaríamos $S(n+1) - S(n)$ estar muy cerca de $S'(n)$y heurísticamente esperaríamos que $S$ satisfacer $S'(n) = S(an)$. Esta ecuación parece un poco difícil de resolver, pero una solución aproximada es$S(n) = n^{\Theta(\log n)}$. Sustituyendo de nuevo, deducimos que el orden de crecimiento de$T(n)$ debería ser algo como $(\log n)^{\Theta(\log \log n)}$.