Complexity Of A Recurrence Summation.

95 Views Asked by At

I was trying to find all possible full trees as a recurrence formula and I found it but now I want to find the complexity of it as $\theta$ relation. I found that it is something like this.

$$f(n)=\sum_{i=0}^{n-1}f(i)*f(n-i-1) \text{ and } f(0)=1,f(1)=1$$

I know it is not exactly this function (I simplified it) but if I can learn how to solve this I can apply it to all possible full trees formula.

TLDR; I want to know how I can find time complexity of $f(n)$

1

There are 1 best solutions below

1
On BEST ANSWER

Turns out Catalan numbers as @kelalaka said was the answer. If modeled correctly many problems like number off all possible binary tree's could be looked in this Catalan numbers perspective. here is more detail.