Time complexity to find out the number of ways to parenthesize N matrices 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.



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.
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&mdash;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.