Resolver la recurrencia

¿Cómo puedo resolver la siguiente relación de recurrencia?

f (n) = f (n - 1) + f (n - \log n)

$f(n) = f(n-1) + f(n - \log n)$

recursion bola de masa de mobius
fuente

¿Qué obtienes si intentas

? Parece que obtendrá un límite inferior de

f (n) = 2 f (n - \log n)

$f(n) = 2f(n - \log n)$

2^{Ω (n / \log n)}

$2^{\Omega(n/\log n)}$

Chandra Chekuri

@ChandraChekuri ¡Oh, eso es genial! Y hay un límite superior de

: utilizamos el

recurrencia

veces, y obtenemos que

. Luego aplicamos este

veces y obtenemos

2^{O (n \log \log n / \log n)}

$2^{O(n \log \log n / \log n)}$

\log n

$\log n$

f (n) \leq (1 + \log n) f (n - \log n)

$f(n) \le (1 + \log n) f(n - \log n)$

n / \log n

$n / \log n$

. Entonces, la brecha entre el límite superior y el límite inferior es solo

en el exponente. Esto es suficiente para mis propósitos, pero dejaré la pregunta abierta en caso de que alguien quiera y pueda cerrar la brecha. Muchas gracias Chandra!

f (n) \leq (1 + \log n)^{n / \log n} = 2^{O (n \log \log n / \log n)}

$f(n) \le (1 + \log n)^{n / \log n} = 2^{O(n \log \log n / \log n)}$

\log \log n

$\log \log n$

mobius dumpling

Bueno, el mismo truco da

, entonces

f (n) \geq (\log n) f (n - 2 \log n)

$f(n)\ge(\log n)f(n-2\log n)$

f (n) = 2^{Θ (n \log \log n / \log n)}

$f(n)=2^{\Theta(n\log\log n/\log n)}$

Emil Jeřábek

Resolver la recurrencia

Respuestas: