The following function produces the nth number in catalan numbers. What is the exact time complexity function of this function or how can I find it myself?
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;
}
Note: I know this is the worst possible way to compute a catalan number.
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 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 :)