Recurrencia extraña: ¿Para qué es asintótica?

Question

Así que tengo la siguiente relación de recurrencia para la tasa de crecimiento de un algoritmo:

$T(n)$ = Tiempo tomado por el algoritmo para resolver el problema de tamaño n:

ps

Claramente esto no obedece a ninguna ley polinomial, pero ahora mi pregunta es ¿a qué obedece?

Sólo quiero una equivalencia asintótica.

Mi conjetura es subexponencial, ya que es más rápido que el polinomio, pero claramente más lento que cualquier forma exponencial.

¿Cuál es sin embargo la pregunta ....

Answer 1

Con $T(1) = 1$, el cálculo de los términos de la secuencia da sucesivamente $1, 2, 4, 6, 10, 14, 20, 26, 36, 46, \dots$, buscando que en OEIS da OEIS secuencia A000123, que es el número de particiones de $2n$ en los poderes de $2$. Aquí, como empezamos con $T(1) =1$ en lugar de $T(0)=1$, debemos decir $T(n)$ es el número de particiones de $2n-2$ en los poderes de $2$.

Podemos estar seguros de que es la misma secuencia, después de una prueba dada aquí: vamos a $A(n)$ denotar el número de particiones de $n$ en los poderes de $2$. Entonces:

• $A(2m+1) = A(2m)$, debido a que cualquier partición de $2m+1$ en los poderes de $2$ debe necesariamente contener "$1$" como una de las partes, y la eliminación se da una partición de $2m$ en los poderes de $2$.
• Del mismo modo, $A(2m+2) = A(2m) + A(m+1)$, debido a que cualquier partición de $2m+2$ en los poderes de $2$ contiene una parte "$1$" (que se puede quitar, por lo que el número de particiones es $A(2m+1) = A(2m)$) o más de todas las partes se puede dividir por $2$ a dar una partición de $m+1$ en los poderes de $2$ (el número de particiones es $A(m+1)$).

Así, supongamos que definimos $B(n) = A(2n-2)$. A continuación, tenga en cuenta que

• al $n$ es incluso, $B(\lceil n/2 \rceil) = A(2(n/2)-2) = A(n-2)$ (sino $A(n-1) = A(n-2)$)
• al $n$ es impar, $B(\lceil n/2 \rceil) = A((n+1) - 2) = A(n-1)$.

Por lo $B(\lceil n/2 \rceil) = A(n-1)$ en ambos casos. Por lo tanto, $B(n)$ satisface la misma recurrencia como $T(n)$: tenemos $B(n) = A(2n-2) = A(2n-4) + A(n-1) = B(n-1) + B(\lceil n/2 \rceil)$, y, por supuesto,$B(1) = 1 = T(1)$, lo $T(n) = B(n)$.

De acuerdo con un comentario por Philippe Flajolet allí, la precisión de los asymptotics de esta secuencia se dan en un papel por N. G. de Bruijn llamado "De Mahler Problema de Partición" (1948, PDF), y es equivalente a:

$$ \log T(n) = \frac{1}{2\log 2}\left(\log \frac{n}{\log n}\right)^2 + \left(\frac12 +\frac1{\log \log 2} + \frac{\log \log 2}{\log 2}\right)\log n - O(\log \log n) $$ (de una manera más precisa la expresión de abajo a la $O(1)$ plazo es que allí se indican).

Esto confirma la idea de que $T(n)$ crece más rápido que el polinomio y lenta que la exponencial, como los polinomios son las funciones de $f$ que $\log f(n) \sim c\log n$ algunos $c$, y las exponenciales son aquellas para las que se $\log f(n) \sim cn$ algunos $c$.

Si desea una forma menos precisa obligado a tener una idea aproximada de su tipo de crecimiento, se puede observar que el $\log T(n) = O\left((\log n)^2\right)$ y, por tanto, $$T(n) = n^{O(\log n)}.$$