Analyzing an algorithm with recurrence T(n) = T(n - 1) + T(n - 2) + T(n -3)?

Question

So, someone posted this question earlier, but essentially no effort was put into it, it was poorly tagged and then closed. Nonetheless, I think it could have been a good question. I'm posting because according to the OP, my answer (posted in a comment) did not agree with the solution. So, I'm trying to figure out what I'm doing incorrectly (assuming that the answer that he has in indeed correct):

We have:

T(N) = T(N-1) + T(N-2) + T(N-3)

where N > 3. He didn't have a base case listed, but since N > 3, I assumed that there are probably 3 base cases for T(3), T(2) and T(1) . To calculate T(K), we do the following:

T(K) = T(K-1) + T(K-2) + T(K-3)

Then we must calculate:

T(K-1) = T((K-1)-1) + T((K-1)-2) + T((K-1)-3)
T(K-2) = T((K-2)-1) + T((K-2)-2) + T((K-2)-3)
T(K-3) = T((K-3)-1) + T((K-3)-2) + T((K-3)-3)

and so on... Here's a tree-representation:

L0                                                  T(K)
                      /                              |                              \
L1               T(K-1)                            T(K-2)                           T(K-3)
          /         |     \                 /        |          \                 /   |     \
L2   T((K-1)-1) T((K-1)-2) T((K-1)-3)  T((K-2)-1) T((K-2)-2) T((K-2)-3) T((K-3)-1) T((K-3)-2) T((K-3)-3)    
                 ...                                ...                                ...

So we have 3 children, then 9 children, then 27 children,..., until we hit our base cases. Hence, the algorithm is O(3^(N-3)), the N-3 is there to account for the three base cases, ie after T(4), we can only have bases cases, no more branching.

The actual solution was never provided, but like I said, I'm told that this is incorrect. Any help would be appreciated.

Answer 1

This is a cool method that I learned, so I thought I'll share it with you.It's really simple to estimate the time complexity. Looking at the recurrence we guess that the time complexity is exponential.

Lets say:

T(N)=x^n

The given recurrence is

T(N) = T(N-1) + T(N-2) + T(N-3)

Substituting

 x^n = x^n-1  + x^n-2  + x^n-3
Dividing throughout by x^n-3
 x^3 = x^2    + x^1    + 1
Rearranging
 x^3 - x^2 - x - 1=0

You can find out it's cubic roots here.

This cubic equation has one real root( 1.8392867552141612) and two complex roots(of magnitude 0.7373527).

Thus asymptotically our algorithm's running time is bounded by T(N)=1.839^n.

Answer 2

The recurrence you have set up is the following:

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

I assume the base cases are probably

T(0) = T(1) = T(2) = 1

If you start to expand out the terms of this recurrence, you get

• T(0) = 1
• T(1) = 1
• T(2) = 1
• T(3) = 3
• T(4) = 5
• T(5) = 9
• T(6) = 17
• T(7) = 31
• ...

There doesn't seem to be an obvious pattern here. Fortunately, we can go to the Online Encyclopedia of Integer Sequences and punch in the terms 1, 1, 1, 3, 5, 9, 17 and you'll find that this is the Tribonacci sequence whose first three terms are 1.

If you look at the information about the Tribonacci numbers, you'll see the following:

a(n)/a(n-1) tends to the tribonacci constant, 1.839286755...

(here, a(n) is the notation the site uses for my T(n)). Since the ratio of consecutive terms of the Tribonacci sequence tends to approximately 1.839286755, we know that the Tribonacci sequence must be exponentially growing, and it grows exponentially at a rate that is approximately Θ(1.839286755ⁿ). (Compare this to the Fibonacci sequence, which is known to grow at Θ(φⁿ), where φ is the golden ratio). Doing some further reading on Wikipedia gives this formula for the Tribonacci constant:

and confirms the exponential growth rate.

Consequently, we can conclude that the runtime is Θ(1.839286755ⁿ).

So... how would you compute this on your own? The easiest way to do this (and I think the way that these values are known) is to use generating functions. You can try to derive a generating function for the recurrence you have written out here, then try to rewrite the generating function in a closed-form to get the exact value. This is one way to get the closed-form for Fibonacci numbers, and it should generalize here (though it might be a lot of slogging through unpleasant math.) Alternatively, as @tmyklebu points out, you could write out this matrix:

     | 0 1 0 |
 M = | 0 0 1 |
     | 1 1 1 |

and compute its eigenvalues, the largest of which will come out to the Tribonacci constant. (Note that this matrix has the property that

 | 0 1 0 |   |a|   |    b    |
 | 0 0 1 | x |b| = |    c    |
 | 1 1 1 |   |c|   |a + b + c|

Consequently, if you put three consecutive values from the recurrence into a column vector v and compute Mv, you get back a new column vector holding the latter two values from the recurrence, plus the next value in the recurrence. In this way, you can compute the kth value of the recurrence by computing M^kv and looking at the first component of the vector.)

Hope this helps!