# Simplifying a T(n) runtime

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`?

-
Order, or exact? The order analysis is easy; the exact analysis involves the Tribonacci sequence. – nneonneo Oct 14 '12 at 6:38
Hmm, can we write this as matrix equations for a linear system? – Mehrdad Oct 14 '12 at 6:39
Yes, you can. Actually, that's how you can solve most linear recurrences. The exact solution is given by just diagonalizing the resulting recurrence matrix. – nneonneo Oct 14 '12 at 6:39
@NickNicolini: "merely find the T(n) run time"... O(n) is easier to find than T(n), not harder! – Mehrdad Oct 14 '12 at 6:41
Yeah, T(n) means exact running time, O(n) would be finding the order of T(n) (which is much easier). – nneonneo Oct 14 '12 at 6:42

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

Then T(n) should be c1 x1n + c2 x2n + c3 x3n - 1/2, where xi are roots of equation x3 - x2 - x - 1 = 0 and ci are specific coefficients.

The accurate solution of T(n) is a bit complex. Actually x1 = 1.84, x2,x3 = -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 c1 xn + c0. Therefore, you cannot simplify it any further.

-
Looks right. I'd check the math but it's getting late :) – nneonneo Oct 14 '12 at 6:50
Clever job with the S(n)! – Mehrdad Oct 14 '12 at 7:19

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

It is

``````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's

``````g(0) = 1
g(1) = 3
g(2) = 5

g(3) = 9 (i.e. = g(0) + g(1) + g(2) = 9, not g(1) + g(2) + g(3) + 1 = 10)
``````

Use dynamic programming to avoid recalculating 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;
}
``````
-

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

after simplifying will give a run time of O(n). 3T(n-1) is not right.

-
No, absolutely wrong. This is not `O(n)` at all. – nneonneo Oct 14 '12 at 6:38
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://stackoverflow.com/questions/12879795/simplifying-a-tn-runtime", "fetch_time": 1464577928000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2016-22/segments/1464049288709.26/warc/CC-MAIN-20160524002128-00225-ip-10-185-217-139.ec2.internal.warc.gz", "warc_record_offset": 276575048, "warc_record_length": 20414, "token_count": 999, "char_count": 2494, "score": 4.0, "int_score": 4, "crawl": "CC-MAIN-2016-22", "snapshot_type": "latest", "language": "en", "language_score": 0.8789212703704834, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00037-of-00064.parquet"}