$T(n) = 2T(\lfloor n/2\rfloor +1) + T(n-1) + 1$ , $T(3) = 1$

Question

Estoy buscando un límite asintótico en $T$ , donde $T$ satisface la siguiente recurrencia: $$T(n) = 2T(\lfloor n/2\rfloor +1) + T(n-1) + 1\text{ , }T(3) = 1.$$

He trazado el gráfico para $T$ y parece que $T$ crece en algún lugar entre un polinomio y un exponencial. Quiero saber si $T$ tiene un crecimiento exponencial o un crecimiento más lento.

Answer 1

Su predicción es correcta, $T(n)$ tiene una tasa de crecimiento entre polinómica y exponencial. Sea $F(x)$ se define por $$ F(x) = \sum_{n=0}^\infty \frac{c_n (x-3)^n}{n!} $$ donde $c_n$ se define por $c_0=1$ y $c_n = 3 \cdot 2^{-\binom{n-1}2}$ para $n\ge 1$ . Esta serie converge (con bastante rapidez, añadiría yo) para todos los $x\in \mathbb{C}$ .

Reclamación: Para todos $n\ge 3$ $$ F(n) \ge T(n) \ge C + (2C+1)F(n+3) $$ donde $C = \frac{1-F(6)}{1+2F(6)} \approx -0.477$ .

Observamos que $F(x)$ tiene claramente una tasa de crecimiento superior al polinomio. Es una función entera de orden $0$ lo que significa que para cualquier $\alpha >0$ , $$ \lim\limits_{x\rightarrow\infty} \frac{F(x)}{\exp(x^\alpha)} = 0 $$ Ver 1 .

Prueba del límite superior: Observamos que $c_{n+1} = 2^{1-n}c_n$ para $n\ge 1$ , lo que implica \begin{eqnarray} F'(x-1) &=& 2F(x/2 + 1) + 1 \end{eqnarray} porque \begin{eqnarray} 2F(x/2 + 1) + 1&=& 1+\sum_{n=0}^{\infty}\frac{2c_n(\frac x2 -2)^n}{n!} \\&=& 1+\sum_{n=0}^\infty \frac{2^{1-n}c_n(x-4)^n}{n!}\\ &=&3 + \sum_{n=1}^\infty \frac{2^{1-n}c_n (x-4)^n}{n!}\\ &=&\sum_{n=0}^\infty\frac{c_{n+1}(x-4)^n}{n!} = F'(x-1).\end{eqnarray}

Afirmamos que $T(n) \le F(n)$ para todos $n\ge3$ que se puede demostrar inductivamente. Es trivial para $n=3$ . Observamos \begin{eqnarray} T(n) &=& 2T(\lfloor n/2 \rfloor + 1)+T(n-1)+1\le 2 F(\lfloor n/2\rfloor + 1) + F(n-1) + 1 \\&\le& 2F(n/2 + 1) + F(n-1) + 1 = F'(n-1) +F(n-1)\\ &=& \int_{n-1}^{n} F'(n-1) dx + F(n-1) \le \int_{n-1}^n F'(x)dx + F(n-1)\\ &=& F(n) \end{eqnarray} donde se aprovecha el hecho de que $F(x)$ es convexo para $x\ge 3$ .

Prueba del límite inferior: Por comodidad, denotemos $G(x) = C + (2C+1)F(x+3)$ . Observamos \begin{eqnarray} G'(x) &=& (2C+1)F'(x+3) = (2C+1)(2F(\frac {x+4}2 + 1) + 1)\\&=&2(2C+1)F(\frac x 2 + 3) + 2C+1=2G(x/2) + 1 \end{eqnarray} y \begin{eqnarray} G(1) &=& C + (2C + 1)F(6) = \frac{1-F(6)}{1+2F(6)} + 2\frac{F(6)-F(6)^2}{1+2F(6)}+F(6)\\ &=&\frac{1 + F(6) - 2F(6)^2}{1+2F(6)}+F(6) = \frac{(1-F(6))(1+2F(6))}{1+2F(6)} + F(6) = 1 \end{eqnarray} Utilizamos la inducción para demostrar que $T(n) \ge G(n)$ para todos $n\ge 3$ Utilizando lo anterior como caso base, procedemos (de nuevo haciendo uso de la convexidad): \begin{eqnarray} T(n)&=&2T(\lfloor n/2 \rfloor + 1) + T(n-1)+1 \ge 2G(\lfloor n/2 \rfloor + 1) + G(n-1) + 1\\ &\ge& 2G(n/2) + G(n-1)+1= G'(n) + G(n-1) \\&\ge& \int_{n-1}^{n}G'(x)dx + G(n-1) = G(n) \end{eqnarray} completando la prueba.

Actualización - Demostración numérica: Después de hacer algunas simulaciones numéricas, parece que $$ \lim_{n\rightarrow\infty} \frac{T(n)}{F(n)} \approx 0.2656... $$ Aquí hay un gráfico de los primeros mil términos de la relación $T(n)/F(n)$ con la línea roja horizontal en $y=0.2656$ : Hice el cálculo hasta $50000$ . La relación se mantiene plana en esa línea. También parece que $$ \log F(x) \sim (\log x)^\alpha$$ para algunos $\alpha \approx 1.81$ .

Answer 2

Una pista.

Suponiendo que $T(k) = 0$ para $k \lt 3$ y considerando

$$ T(n) = a T\left(\lfloor\frac n2\rfloor + 1\right)+T(n-1)+1 $$

y el desarrollo de $n=4$

$$ \begin{array}{ll} n & T(n) \\ 4 & a T(3) + T(3) + 1 \\ 5 & a T(3) + T(4) + 1\\ 6 & a T(4) + T(5) + 1\\ 7 & a T(4) + T(6) + 1\\ \vdots & \vdots \\ \end{array} $$

y después de sumar término a término tenemos

$$ \sum_{k=4}^n T(k) = 2a \sum_{k=3}^{\lfloor\frac n2\rfloor + 1}T(k) + \sum_{k=3}^{n-1}T(k)+n-3 $$

o mejor

$$ \cases{ T(2n)= T(3) + 2a \sum_{k=3}^{n + 1}T(k) + n-3 - a T(n+1)\\ T(2n+1)= T(3) + 2a \sum_{k=3}^{n + 1}T(k) + n-3 } $$

que puede expresarse como una función polinómica de $(a,T(3))$ . Los grados de los polinomios son según la tabla

$$ \begin{array}{ll} n = 3 & 0\\ n\in [3+1, 3+2] & 1\\ n\in [3+3, 3+6] & 2\\ n\in [3+7, 3+14] & 3\\ \vdots & \vdots\\ n\in [3+2^{\theta}-1,3+2^{\theta+1}-2] & \theta \end{array} $$

Polinomios típicos

$$ \begin{array}{ll} n & T(n)\\ 3 & 1\\ 5 & 3+2a\\ 9 & 7 + 12 a + 6a^2\\ 10 & 8 + 16a+10a^2+a^3\\ 17 & 15 + 56a + 68a^2 + 26a^3\\ 52 & 50 + 625 a + 2600 a^2 + 4004 a^3 + 2264 a^4 + 284 a^5\\ 99 & 97 + 2352 a + 19000 a^2 + 57356 a^3 + 67746 a^4 + 29164 a^5 + 2030 a^6 \end{array} $$