8

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.

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Amen
  • 1,524
  • 5
  • 22
  • 41
  • 2
    There are certainly cases in which you can't use it, but for finding the computational complexity of recursive functions, I would look into [recurrence relations](http://www.cs.duke.edu/~ola/ap/recurrence.html) and the [Master Theorem](http://en.wikipedia.org/wiki/Master_theorem). – nchen24 Dec 09 '14 at 05:00

3 Answers3

15

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

10

Assume

  1. any step other than for-loop is k;
  2. summation and multiple in for-loop is c and
  3. catalan(r) is T(r)

In the for-loop of catalan(n), catalan(i) performs n-1 times where value of i from 1 to n-1 and catalan(n-i) performs n-1 times where value of n-i from n-1 to 1. In short, catalan(i) and catalan(n-i) equals to two times all catalan(x) where value of x from 1 to n-1.

T(n) = 2(T(1) + T(2) + T(3) + ... + T(n-2) + T(n-1)) + k + (n-1)c
Similarly, 
T(n-1) = 2(T(1) + T(2) + T(3) + ... + T(n-2)) + k + (n-2)c

Reorder T(n) as 2(T(1) + T(2) + T(3) + ... + T(n-2)) + 2T(n-1) + k + (n-2)c + c
T(n) = 2(T(1) + T(2) + T(3) + ... + T(n-2)) + k + (n-2)c + 2T(n-1) + c
T(n) = T(n-1) + 2T(n-1) + c
T(n) = 3T(n-1) + c
T(n) = (3^2)T(n-2) + 3c + c
T(n) = (3^3)T(n-3) + (3^2)c + 3c + c
and so on...
T(n) = (3^(n-1))T(n-(n-1)) + c(3^0 + 3^1 + 3^2 + ... + 3^(n-2))
T(n) = (3^(n-1))T(1) + ((3^(n-1)-1)/2)c

So, the time complexity is O(3 ^ N)

hk6279
  • 1,881
  • 2
  • 22
  • 32
2

My process is quite similar to @hk6279's one but I believe easier to understand because I start from the code itself. I start defining the recurrence relation as it is in code and then substitute it.

I also remove all the + k + c variables from @hk6279's approach because it adds noise to the equation and at the end all those variables will be ruled out.

Recurrence relation

T(n) => 1             -> n = 1
        T(i) * T(n-i) -> n > 1; for i in 1..n-1

Visualize when n > 1

T(n) = [T(1) + T(2) + T(3) + .... + T(n-2) + T(n-1)] + [T(n-1) + T(n-2) + .... + T(3) + T(2) + T(1)]
T(n) = [T(1) + T(2) + T(3) + .... + T(n-2) + T(n-1)] + [T(1) + T(2) + T(3) + .... + T(n-2) + T(n-1)]
T(n) = 2 * [T(1) + T(2) + T(3) + .... + T(n-2) + T(n-1)]

What is T(n-1) ?

T(n-1) = 2 * [T(1) + T(2) + T(3) + .... + T(n-2)]

Replace with T(n-1)

T(n) = 2 * [T(1) + T(2) + T(3) + .... + T(n-2) + T(n-1)]
T(n) = 2 * [T(1) + T(2) + T(3) + .... + T(n-2)] + 2 * [T(n-1)]
T(n) = T(n-1) + 2 * [T(n-1)]
T(n) = 3 * T(n-1)

What is T(n-2) ?

T(n-2) = 2 * [T(1) + T(2) + T(3) + .... + T(n-3)]

Replace with T(n-2)

T(n) = 3 * [2 * [T(1) + T(2) + T(3) + .... + T(n-3) + T(n-2)]]
T(n) = 3 * [2 * [T(1) + T(2) + T(3) + .... + T(n-3)] + 2 * T(n-2)]]
T(n) = 3 * [T(n-2) + 2*T(n-2)]
T(n) = 3 * [3 * T(n-2)]
T(n) = 3^2 * T(n-2)

Replace with T(n-k)

T(n) = 3^k * T(n-k)

if n - k = 1 => k = n + 1

T(n) = 3^(n+1) * T(n-n+1)
T(n) = 3^(n+1) * T(1)
T(n) = 3^(n+1) * 1

Time complexiTy

O(3^n)
Daniel Botero Correa
  • 556
  • 6
  • 16