Как решить Т (п) = Т (п-2) + T (2) + п с рекурсии дерева

Question

Я хочу найти сложность алгоритма, который включает в себя повторение:

Т (п) = T (n-2) + T (2) + n

T (n) - время, необходимое для решения проблемы размера n. Я хочу использовать дерево рекурсии, но моя проблема - T (2), мы можем считать, что T (2) будет доминировать T (n-2).

Answer 1

Допустим, вы начать с

T (N) = Т (п - 2) + T (2) + п.

Затем

Т (п) =

Т (п - 2) + T (2) + п =

Т (п - 4) + 2T (2) + п + (п - 2) =

Т (п - 6) + 3T (2) + п + (п - 2) + (N - 4) =

...

Т (к) + Θ (п) Т (2) + ∑ _{я = п, п - 2, ..., к} [I]

где k - некоторая константа.

В последнем выражении,

Т (2) является константой, так что Θ (п) Т (2) = Θ (п). Также

∑ _{я = п, п - 2, ..., к} [I] = Θ (п), так как это арифметическое серии.

В целом, Т (п) = Θ (п).