T (n-1) + 1/lg (n) повторяемость

Question

Я ищу верхнюю и нижнюю границу (или просто привязанность к тете, если на то пошло).

T(n) = T(n-1) + 1/lg(n) 

Я изучаю тест, и это один из практических вопросов, на которые я застрял.

Answer 1

я полагаю, что разложение даст вам соответствующую подсказку:

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)

Теперь используйте теорему Учителя об этом новом повторении.