Search code examples
algorithmcomplexity-theorytime-complexityrecurrenceasymptotic-complexity

Complexity of the recursion: T(n) = T(n-1) + T(n-2) + C

I want to understand how to arrive at the complexity of the below recurrence relation.

T(n) = T(n-1) + T(n-2) + C Given T(1) = C and T(2) = 2C;

Generally for equations like T(n) = 2T(n/2) + C (Given T(1) = C), I use the following method.

T(n) = 2T(n/2) + C
=> T(n) = 4T(n/4) + 3C
=> T(n) = 8T(n/8) + 7C
=> ...
=> T(n) = 2^k T (n/2^k) + (2^k - 1) c

Now when n/2^k = 1 => K = log (n) (to the base 2)

T(n) = n T(1) + (n-1)C
     = (2n -1) C
     = O(n)

But, I'm not able to come up with similar approach for the problem I have in question. Please correct me if my approach is incorrect.

Solution

  • The complexity is related to input-size, where each call produce a binary-tree of calls

    Where T(n) make 2n calls in total ..

    T(n) = T(n-1) + T(n-2) + C

    T(n) = O(2n-1) + O(2n-2) + O(1)

    O(2n)

    In the same fashion, you can generalize your recursive function, as a Fibonacci number

    T(n) = F(n) + ( C * 2n)

    Next you can use a direct formula instead of recursive way

    Using a complex method known as Binet's Formula