Search code examples
algorithmmathbig-otime-complexityrecurrence

What's the run time of: T(n) = 2T(n-1) + 3T(n-2)+ 1

I understand that it is similar to the Fibonacci sequence that has an exponential running time. However this recurrence relation has more branches. What are the asymptotic bounds of T(n) = 2T(n-1) + 3T(n-2)+ 1?

Solution

  • Usually, you will need to make some assumptions on T(0) and T(1), because there will be exponentially many of them and their values may determine the functional form of T(n). However in this case it doesn't seem to matter.

    Then, recurrence relations of this form can be solved by finding their characteristic polynomials. I found this article: http://www.wikihow.com/Solve-Recurrence-Relations

    I obtained the characteristic polynomial with roots 3 and 1, so that guesses the form T(n) = c_1*3^n + c_2. In particular, T(n) = 1/2*3^n - 1/4 satisfies the recurrence relation, and we can verify this.

    1/2*3^n - 1/4 = 2*T(n-1) + 3*T(n-2) + 1
              = 2*(1/2*3^(n-1) - 1/4) + 3*(1/2*3^(n-2) - 1/4) + 1
              = 3^(n-1) - 1/2 + 1/2*3^(n-1) - 3/4 + 1
              = 3/2*3^(n-1) - 1/4
              = 1/2*3^n - 1/4

    Hence it would give that T(n) = Theta(3^n). However, this may not be the only function that satisfies the recurrence and other possibilities will also depend on what you defined the values T(0) and T(1), but they should all be O(3^n).