Analysis of the algorithm with repetition T (n) = T (n - 1) + T (n - 2) + T (n -3)?

Question

So, someone posted this question earlier, but there was no effort in it, it was badly marked and then closed. However, I think it could be a good question. I am posting because, according to the OP, my answer (posted in the comment) does not agree with the solution. So, I'm trying to figure out what I'm doing wrong (assuming that he is really right):

We have:

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

where N> 3. He did not have a base register, but since N> 3, I assumed that for T(3) , T(2) and T(1) 3 basic cases are possible. 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 view:

 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 on our basic cases. Therefore, the algorithm O(3^(N-3)) , N-3 must take into account three basic cases, i.e. After T (4), we can only have basic cases, no more branching.

The actual solution was never provided, but, as I said, I was told that this is not true. Any help would be appreciated.

Answer 1

The repeat you configured is as follows:

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

I guess the base cases are probably

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

If you begin to expand the conditions of this repetition, 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 seems to be no obvious picture here. Fortunately, we can go to the Online Encyclopedia of Integer Sequences and perforate in terms of 1, 1, 1, 3, 5, 9, 17, and you will find that this is a tribonacci sequence , the first three conditions of which are equal to 1.

If you look at the information on the Tribonacci numbers, you will see the following:

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

(here (n) is the designation that the site uses for my T (n)). Since the ratio of consecutive members of the Tribonacci sequence tends to be approximately 1.839286755, we know that the Tribonacci sequence should increase exponentially, and it grows exponentially at a rate that is approximately equal to & Theta (1.839286755 ⁿ ). (Compare this to the Fibonacci sequence, which is known to grow in? Theta; (? Phis; ⁿ ), where? Is the golden ratio). Further reading of Wikipedia gives this formula for the Tribonacci constant:

and confirms the exponential growth rate.

Therefore, we can conclude that the lead time is: & theta; (1.839286755 ⁿ ).

So ... how would you calculate this yourself? The easiest way to do this (and I think these values ​​are known) is to use function generation . You can try to get a generating function for the repetition you are repeating, and then try to overwrite the generation function in a closed form to get the exact value. This is one way to get a closed form for Fibonacci numbers, and it should be generalized here (although it can be a lot of traffic jams through unpleasant mathematics). Alternatively, as @tmyklebu points out, you can write this matrix:

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

and calculate its eigenvalues, the largest of which will go 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| 

Therefore, if you put three consecutive values ​​from a repetition into a column vector v and calculate Mv, you return a new column vector that keeps the last two values ​​from repeating, plus the next value in the repetition. Thus, you can calculate the kth repetition value by calculating M ^k v and looking at the first component of the vector.)

Hope this helps!

Answer 2

This is a cool method that I learned, so I thought I would share it with you. It is very easy to evaluate the time complexity. Considering the repetition, we assume that the time complexity is exponential.

Let's say:

 T(N)=x^n 

This recurrent

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

Substitution

  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 the cubic roots here .

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

Thus, asymptotically, our algorithm running time is limited by T (N) = 1.839 ^ n .

Answer 3

As some people have noted, this repetition is different from the original repetition T(N) = T(N-1) + T(N-2) - T(N-3) . I prefer the approach assuming T(N)=x^N given by @Aravind. With this repetition, you get the characteristic equation x^3-x^2-x+1=(x-1)^2(x+1) . (This will be the characteristic equation for the @templatetypedef matrix approach and the denominator of the generating function, if you take this approach.)

A repeating root causes all kinds of difficulties. The matrix is ​​not diagonalizable. The generating function has a repeated denominator when you define it. When you take T(N)=x^N , you get only two linearly independent solutions and need a third.

In the general case, when you take T(N)=x^N and get the double root r , this means that the linearly independent solutions are r^N and N*r^N (the triple root introduces N^2*r^N ). Thus, in our case, three linearly independent recurrence solutions are (-1)^N , 1^N=1 and N*1^N=N This means that the general solution is T(N)=A(-1)^N+B+C*N , and you use the initial conditions to determine A , B and C If C!=0 , then T(N)=Θ(N) , otherwise T(N)=Θ(1) . This is probably not so realistic for the algorithm.