Simplified runtime T (n)

Question

Given the following function

int g(int y) { if (y <= 0) { return 1; } else { return g(y-1) + g(y-2) + g(y-3); } } 

We need to find the execution time T(n) . Now I know that you can write

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

I'm just not sure you can simplify this, for example T(n) = 3T(n-1) + 1 ?

Answer 1

Let S (n) = T (n) + 1/2 , then S (n) = S (n-1) + S (n-2) + S (n-3) .

Then T (n) should be c ₁ x ₁ ⁿ + c ₂ x ₂ ⁿ + c ₃ x ₃ ⁿ - 1/2 , where x _i are the roots of the equation x ³ - x ² - x - 1 = 0 and c _i are specific factors.

The exact solution T (n) is a little more complicated. In fact x ₁ = 1.84, x ₂ , x ₃ = -0.42 ± 0.61i (yes, they are not real numbers).

However, if T (n) can be simplified to form as T (n) = 3T (n-1) + 1 , then T (n) should be like c ₁ x ⁿ + c ₀ . Therefore, you cannot simplify it.

Answer 2

Your function is not

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

it

 if n > 2 T(n) = T(n-1) + T(n-2) + T(n-3) or T(n) = 1, 3, 5 for n = 0, 1, 2 respectively. 

To check, run your original function with the following "y"

 g(0) = 1 g(1) = 3 g(2) = 5 g(3) = 9 (ie = g(0) + g(1) + g(2) = 9, not g(1) + g(2) + g(3) + 1 = 10) 

Use dynamic programming to avoid recalculating the already calculated T (n) s

 int g(int y) { if(y <= 0) return 1; if(y == 1) return 3; if(y == 2) return 5; int a1 = 1; int a2 = 3; int a3 = 5; int ret = 1; for(int i = 2; i < y; ++i) { ret = a1 + a2 + a3; a1 = a2; a2 = a3; a3 = ret; } return ret; }