Catalan Numbers, Recursive function time complexity

Question

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.

Answer 1

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 :)