Estoy buscando un límite superior Y inferior (o simplemente un límite theta, para el caso).
T(n) = T(n-1) + 1/lg(n)
Estoy estudiando para un examen, y esta es una de las preguntas de práctica en las que me he quedado atascado.
Respuestas
1 para la respuesta № 1Supongo que la siguiente expansión le dará la pista adecuada:
T (n) =
= 1 / lg (n) + T (n-1)
= 1 / lg (n) + 1 / lg (n-1) + T (n-2)
= 1 / lg (n) + 1 / lg (n-1) + 1 / lg (n-2) + T (n-3)
= ···
= 1 / lg (n) + ··· + 1 / lg (n / 2) + T (n / 2)
= Theta (n / lg (n)) + T (n / 2)
Ahora, use el teorema de Master en esta nueva recurrencia.