4
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You can prove stuff in whatever way you want. Mathematics is a free world. $\endgroup$ – Yuval Filmus May 5 '16 at 7:40
  • $\begingroup$ @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! $\endgroup$ – logo_writer May 5 '16 at 7:44
  • 1
    $\begingroup$ If you're expected to use a specific method, switch instructors. $\endgroup$ – Yuval Filmus May 5 '16 at 7:46
  • $\begingroup$ 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)$? $\endgroup$ – Raphael♦ May 5 '16 at 11:38
  • 1
    $\begingroup$ Then the answer is wrong. Assuming the uniform cost model, there's a quadratic-time algorithm. Hint: memoization. $\endgroup$ – Raphael♦ May 5 '16 at 19:11
4
$\begingroup$

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$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – logo_writer May 9 '16 at 2:15
2
$\begingroup$

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 my reasoning is flawed, please leave a comment and I'll edit accordingly.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 9 '16 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.