Search code examples
algorithmtime-complexityrecurrence

Solving the Recurrence Relation T(n)=T(n-1)*T(n-2)+c where T(0)=1 and T(1)=2

I need to solve the recurrence relation for

T(n) = T(n - 1) * T(n - 2) + c    where T(0) = 1 and T(1) = 2.

The algorithm computes 2f(n) where f(n) is the nth Fibonacci number. I assume that T(n - 2) is approximately equal to T(n - 1) and then I rewrite the relation as

T(n) = T(n - 1)^2 + c

and finality I reach to complexity of O(n). This the algorithm:

Power(n):
    if n == 0 then x = 1;
    else if n == 1 then x = 2;
    else x = Power(n - 1) * Power(n - 2);
    return x;

Is it true that the recurrence relation T(n) = T(n - 1) * T(n - 2) + c has O(n) complexity?

Solution

  • You are confusing multiplication in the algorithm with multiplication in the recurrence relation. You calculate Power(n - 1) and Power(n - 2) and multiply them, but this does not take T(n - 1) * T(n - 2) time. These values are computed separately, and then multiplied, taking T(n - 1) + T(n - 2) time, assuming constant-time multiplication.

    The recurrence then becomes T(n) = T(n - 1) + T(n - 2) + c. We'll solve this by substitution. I'll skip choosing an n0; our induction hypothesis will be T(n) = d * 2^n - 1. (We need the -1 to allow of to later cancel the c; this is called strengthening the induction hypothesis, see e.g. here).

    T(n) = T(n - 1) + T(n - 2) + c
     = d * (2^(n - 1) - 1) + d * (2^(n - 2) - 1) + c    (substitute by IH)
     = 3d * 2^(n - 2) - 2d + c
    <= d * 2^n - 2d + c                                 (3 < 2^2)
    <= d * 2^n                                          (when d > c / 2)

    Conclusion: T(n) ∈ O(2n).

    Bonus fact: the tight bound is actually Θ(φn), where φ is the golden ratio. See this answer for an explanation.