нахождение временной сложности рекуррентного соотношения в алгоритмах

Question

Может кто-нибудь помочь мне найти сложность времени

T (n) = 1, если n <= 0 Т (п) = Т (п-1) + Т (п-2) + п </p>

Answer 1

Рассмотрим

F(n) = T(n) + n + 3.

Это дает нам

F(n) - (n+3) = F(n-1) - (n-1+3)  + F(n-2) - (n-2+3) + n

i.e

F(n) - 3 = F(n-1) - 2 + F(n-2) - 1

i.e

F(n) = F(n-1) + F(n-2)

, которая является последовательностью, подобной Фибоначчи!

Хорошо известно, что для последовательностей, подобных Фибоначчи, F(n) = Theta(phi^n) где фи - золотое сечение.

Answer 2

Согласно OEIS , замкнутая формула для этой функции равна , что означает, что асимптотическая сложность этих функций равна .