Я изучаю структуры данных, и у меня возникли некоторые трудности при решении этого вопроса о рекуррентных отношениях:
Решите следующие рекурсии, получив оценку θ для
T(N) given that T(1) = θ(1):
T(N) = 2N - 1 + T(N-1)
Моя работа:
T(N) = 2N - 1 + T(N-1)
T(N-1) = 4N - 2 + T(N-2)
T(N-2) = 6(N - 2)-1 + T(N-3)
T(2) = 2 + T(1)
T(1) = 1 + T(0)
.
.
.
kth step:
T(N) = 2*k*N + T(N-k)
Ответ в книге:
T(N) = 2*k*N^2 + T(N-k)
Не уверен, как они получили N ^ 2. Любая помощь будет принята с благодарностью.