Is there a way to rewrite this recursive function so that it can be calculated in linear time?

Question

I have this recursive function: $$ f(0)=f(1)=1 \\ f(x)=\sum_{i=0}^{x} f(i)×f(x-1-i) $$

The sequence turns out to be $1,1,2,5,14,42, \dotsc$

I want to be able to calculate the nth element quickly. I think doing it in sequence takes $\operatorname{O}(n^2)$ time.

Thanks for any help and please consider I have not formally learnt higher maths.

For those interested I came up with this from a computer science problem I found, where there are $2n$ dots spread like a polygon and you must calculate in how many ways can the dots be joined to pairs without intersections. I reduced the problem to the recursive formula above.

EDIT thanks, i meant linear time. And I see there are some proofs on wikipedia on how to reduce it, unfortunately I am not at the adequate mathematical level to understand them.

Answer 1

As Fred Kline mentions in his comment, there is an explicit formula: $$ f(x) = \frac{(2x)!}{x!(x+1)!}. $$ This allows you to compute $f(x)$ using a linear number of arithmetic operations. You should be aware of the fact that $f(x)$ increases rapidly, and so arithmetic cannot be considered an $O(1)$ operation.

Answer 2

You have to remember certain values (like factorials or binomial coefficients) in order to calculate this quickly. There's no easy way to calculate this in linear time, as its formula is not so simple (even if you know the closed form i.e. the formula for the n-th member). You can try using memoization of some sort.

http://en.wikipedia.org/wiki/Memoization