[Teoria złożoności] Udowodnij złożoność

[eugeno]

1.Mam algorytm:

Kod: Zaznacz cały

G(n)
      if n<=1
           return n
           else return 5*G(n-1)-6*G(n-2)

Muszę udowodnić, że program ten ma złożoność \(\displaystyle{ O(2^{n})}\). Nie mam pojęcia jak to pokazać, pomoże ktoś?

[bartek118]

Jak rozumiem - liczymy mnożenia i dodawania? Czy tylko mnożenia?
Jak tylko mnożenia to masz rekurencję:
\(\displaystyle{ T(n) = T(n-1) + T(n-2) + 2}\)
Jeżeli także dodawania:
\(\displaystyle{ T(n) = T(n-1) + T(n-2) + 5}\)
Tak, czy owak, złożoność wyjdzie taka sama.