# How to calculate the time complexity of a Catalan-like recurrence by substitution?

I was given the following problem:

Calculate the computational time complexity of the recurrence $$P(n) = \begin{cases} 1 & \text{if } n = 1 \\ \sum_{k=1}^{n-1} P(k) P(n-k) & \text{if } n \geq 2 \end{cases}$$ using the substitution method. Answer: $\Omega(2^n)$.

I have seen there is a closed-form for this recurrence but I am unsure whether it can be used out of the blue or not. I don't know if I have to prove it by deriving it from the recurrence or if there are simpler ways of solving such a problem by mere substitution.

On the other hand, I think substitution is not the right tool to use here. I have tried with both reverse and forward substitution, but in neither approach I could determine the function as with other problems (e.g. QuickSort).

Is it possible to solve this problem with only substitution at all? If so, how can I devise it?

• You can prove stuff in whatever way you want. Mathematics is a free world. – Yuval Filmus May 5 '16 at 7:40
• @YuvalFilmus I know, but when I'm expected to use a specific method, I have to stick to it. Your induction approach is impressive, though. It's elegant for me! – logo_writer May 5 '16 at 7:44
• If you're expected to use a specific method, switch instructors. – Yuval Filmus May 5 '16 at 7:46
• I don't understand the problem statement. Are you supposed the recurrences for $P(n)$, or are you supposed to determine the time needed to compute $P(n)$? – Raphael May 5 '16 at 11:38
• Then the answer is wrong. Assuming the uniform cost model, there's a quadratic-time algorithm. Hint: memoization. – Raphael May 5 '16 at 19:11

You can use induction. First, check directly that $P(n) \geq 2^{n-2}$ for all $n \leq 4$ (the relevant values are $1,1,2,5$). Now suppose that $P(n) \geq 2^{n-2}$ holds for all $n \leq m$, where $m \geq 4$. Then $$P(m+1) = \sum_{k=1}^m P(k) P(m+1-k) \geq \sum_{k=1}^m 2^{k-2} 2^{m+1-k-2} \geq m 2^{m+1-4} \geq 2^{m+1-2},$$ since $m \geq 4$.

• Your approach is really elegant! As it uses no other formulas than the ones given, I really like it. On a side note, after talking with my instructor, I have found another way. Feel free to check my answer and comment is something is flawed. Thank you again! – logo_writer May 9 '16 at 2:15

For the record, I'll describe here the procedure that I was looking for (after being oriented by my instructor).

1. A closed form was indeed needed to solve the problem. From here, I took this recurrence:

$$P(0) = 1, P(n+1) = \frac{2(2n+1)}{n+2} \cdot P(n)$$

1. Using reverse substitution, and then letting $j = (n-k)+2$, I ended up with

$$P(n) = 2^n \prod_{k=1}^{n} \frac{2(n-k)+1}{(n-k)+2} = 2^n \prod_{j=2}^{n+1} \frac{2j-3}{j} = 2^n \prod_{j=2}^{n+1} \left( 2 - \frac{3}{j} \right)$$

1. I proved by induction that $P(n) \geq 2^n\ \forall\ n \geq 5$, in order to use $n_0 = 5$ in the formal definition of $\Omega[f(n)]$, which for completeness, is

$$\Omega[f(n)] = \{g(n) \mid \exists\ c > 0, n_0 > 0 : 0 \leq cg(n) \leq f(n)\ \forall\ n \geq n_0\}$$

1. Finally, using $n_0 = 5$ and the formal definition, it is shown $P(n) \in \Omega(2^n)$.

• If you know the solution in closed form, there are other methods to estimate its asymptotics. For example, Wikipedia mentions that $P(n) \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$, which follows from Stirling's formula. – Yuval Filmus May 9 '16 at 10:15