Time complexity to find out the number of ways to parenthesize N matrices

Question

I am trying to figure out the $time$ $complexity$ to find out the number of ways we can parenthesize $N$ $matrices$. I have approached this problem as, say if we have $N+1$ matrices then we can parenthesize them in $\dfrac{2N \choose N}{N+1}$ ways

For example, see the below image, here we have 3 matrices which we can represent in a tree and we have 2 nodes which we can arrange to form different unlabeled binary trees in $\dfrac{2N \choose N}{N+1}$ ways which in turn will give us the number of ways in which we can parenthesize these 3 matrices.

enter image description here

But the problem I am facing is that I am unable to figure out the time complexity which this method will take. Any help will be highly appreciated.

Answer 1

These are called Catalan numbers, and the term $\binom{2N}{N}$ is called a central binomial coefficient.

There are several formulas for these numbers which can be used to compute them efficiently, such as the one you present, or

$$C_n = \prod_{k=2}^n \frac{n+k}{k}$$

The problem with writing down the time complexity for computing these numbers is that the Catalan numbers grow exponentially—the number of bits in the output is roughly proportional to the input index. Therefore, the exact time complexity for evaluating these numbers from such a formula is going to depend significantly on the time complexity of your arithmetic operations, especially your choice of multiplication algorithm for large numbers.