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?

Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
Anne
  • 81
  • 2
  • 6
  • If you know the starting terms, you can write it out by hand. T(0) = ? T(1)= ?. From that you can get the rest of the terms – Jason Feb 20 '13 at 21:57
  • 2
    The number of branches in t(n) = F(t(n-1),t(n-2)) is the same for any F, so if you have the solution for the Fibonacci sequence, ... – Joni Feb 20 '13 at 22:15

2 Answers2

1

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).

Andrew Mao
  • 35,740
  • 23
  • 143
  • 224
  • This does not actually answer the question. –  Feb 20 '13 at 23:49
  • Why doesn't it solve the question? I give you a function that satisfies the recurrence relation and proved as such. – Andrew Mao Feb 21 '13 at 01:07
  • Because the question had ABSOLUTELY NOTHING to do with an analytical solution. –  Feb 21 '13 at 03:24
  • You are being really disrespectful. I don't think you understood the question at all, and now you are trolling two people that tried to answer it. `T(n)` is the running time for an algorithm on a particular input of size `n`, and the recurrence relation defines its structure with recursion. We are trying to solve for `T(n)` using this recurrence relation. What do you think the question is about? Perhaps you should answer it if you think you're such a hotshot. – Andrew Mao Feb 21 '13 at 04:16
  • A fibonacci type recurrence relation (when applied recursively) will have exponentially many recursive calls. This is the comment about exponential run time. Your answer fails to touch on the branching aspect. –  Feb 21 '13 at 13:40
  • O(3^n) is exponential in n. Moreover, the **linear recurrence** that people are talking about refers to the polynomial that is solved, not the equation itself. Finding the branching factor for a linear recurrence relation rarely involves counting the branches by hand. In fact, this is how you can also obtain the golden ratio from the Fibonacci recurrence: http://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratio, which, elegantly, would be the branching factor - O(phi^n) if you ran an algorithm with the same recurrence. – Andrew Mao Feb 21 '13 at 14:47
1

This type of recurrences are called: non-homogeneous recurrence relations and you have to solve in the beginning homogeneous recurrence (the one without a constant at the end). If you are interested, read the math behind it.

I will show you an easy way. Just type your equation in wolfram-alpha and you will get:

enter image description here,

which is clearly an exponential complexity: O(3^n)

Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
  • `T(n) = ... which is clearly an exponential complexity: O(3^n)` The `O(3^n) ` in both your and @AndrewMao's answers is the asymptotic `T(n)` *behavior* of the values. It is *not* the algorithmic complexity of calculating `T(n)` (note that the original question is tagged as `algorithm` and `time-complexity`). The time-complexity of running the iteration as written is indeed exponential, but calculating `T(n)` from the explicit formula has practical time-complexity `O(log n)` ([Time complexity of power()](http://stackoverflow.com/questions/5231096/time-complexity-of-power)). – dxiv Dec 20 '15 at 03:57