Question

let T(n) a function of complexity satisfying T(0)=T(1)=Θ(1) and T(n)=Θ(n)+T(n−1)+T(n−2). what is the class of complexity of T(n) ?

Comments

exponential

Answer 1

Consider this function as

• T(n) = 1 when n=1 
• T(n) = 2T(n-1) + n when n>1  

No need to worry about small constant differences like T(n-1) + T(n-2) written as T(n-1) + T(n-1).

Here, while solving this we multiply in the middle by 2 because that was a case of AP & GP together in the series so we neglect the AP one and solve the GP easily.

Complexity Class : Exponential