Simplifying a T(n) runtime

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 T(n) run time. Now, I know that you can write

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

I'm just not sure if you can simplify this any further, such as 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 roots of equation x³ - x² - x - 1 = 0 and c_i are specific coefficients.

The accurate solution of T(n) is a bit complex. Actually x₁ = 1.84, x₂,x₃ = -0.42 ± 0.61i (yes, they are not real numbers).

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