The below solution is taken from Stack Overflow which has a very large number of up votes and it was accepted also, but I have a very very small doubt in this.
The solution is the exact copy I didn't change anything. Since the question is very old, no one seems to reply there.
The following function produces the nth number in Catalan numbers. Actually I have doubt regarding the time complexity of this problem.
int catalan(int n)
{
if (n==0 || n==1)
return 1;
int sum = 0;
for(int i=1;i<n;i++)
sum += catalan(i)*catalan(n-i);
return sum;
}
Here is the solution:
My doubt:
Why is it $c(n+1)-c(n)=2+2c(n)$ ? It should be $c(n+1)-c(n)=2c(n)$ because all terms till $c(n-1)$ will be cancelled in line number 6.
To evaluate the complexity, let us focus on the number of recursive calls performed, let $C(n)$.
A call for $n$ implies exactly $2(n-1)$ recursive calls, each of them adding their own costs, $2(C(1)+C(2)+...C(n-1))$.
A call for $n+1$ implies exactly $2n$ recursive calls, each of them adding their own costs, $2(C(1)+C(2)+...C(n-1)+C(n))$.
By difference, $C(n+1)-C(n) = 2+2C(n)$, which can be written $C(n) = 2+3C(n-1)$.
C(1) = 0
C(2) = 2+2C(1) = 2+3C(0) = 2
C(3) = 4+2(C(1)+C(2)) = 2+3C(2) = 8
C(3) = 6+2(C(1)+C(2)+C(3)) = 2+3C(3) = 26
C(4) = 8+2(C(1)+C(2)+C(3)+C(4)) = 2+3C(4) = 80
...
C(n) = 2n-2+2(C(1)+C(2)+...C(n-1)) = 2+3C(n-1)
To solve this recurrence easily, notice that
C(n)+1 = 3(C(n-1)+1) = 9(C(n-2)+1) = ...3^(n-2)(C(2)+1) = 3^(n-1)
Hence, for $n>1$ the exact formula is
C(n) = 3^(n-1)-1
The number of calls to Catalan(1) (constant time), is also $C(n)$, and the numbers of adds or multiplies are $\frac{C(n)}{2}$ each.
It is easy to reduce the complexity from $O(3^n)$ to $O(2^n)$ by noting that all terms in the loop (except the middle one) are computed twice - but that still doesn't make it an acceptable implementation :)