Търся горна и долна граница (или само тета обвързана, за този въпрос).
T(n) = T(n-1) + 1/lg(n)
Аз изучавам за тест и това е един от практическите въпроси, на които съм се задържал.
Отговори:
1 за отговор № 1Предполагам, че следното разширяване ще ви даде подходящия намек:
T (n) =
= 1 / lg (n) + Т (п-1)
= 1 / lg (n) + 1 / lg (n-1) + T (n-2)
(N-1) + 1 / lg (n-2) + T (n-3)
= ···
= 1 / lg (n) + ··· + 1 / lg (n / 2) + T (n / 2)
= Тета (n / lg (n)) + T (n / 2)
Сега използвайте теоремата "Master" за това ново повторение.