An alternating permutation (or zigzag permutation) of the set $\{1, 2, 3, \dots, n\}$ is an arrangement of those numbers so that each entry is alternately greater or less than the preceding entry. (Taken from here)
So, We want an algorithm to find the number of alternating permutations of $\{1, 2, 3, \dots, n\}$.
Actually, The question has 2 parts:
a) Provide an algorithm in $O(n^3)$ time complexity and $O(n^2)$ space complexity to find the alternating permutations of $\{1, 2, 3, \dots, n\}$.
b) Provide an algorithm in $O(n^3)$ time complexity, and $O(n)$ space complexity to find the number of alternating permutations of $\{1, 2, 3, \dots, n\}$
There is a recursive formula in the link. But, I can't understand what it does. According to the link, This is called André's problem, and the recursive formula for it is:
$2A_{n+1}=\sum_{k=0}^{n} {n \choose k} A_k A_{n-k}$
But, I have two concerns about this formula.
First, What is the time complexity of it? Is it $O(n^3)$, just like the question wants?
My second concern goes for the space complexity of it.
Any idea?
Note: This problem should be solved using the dynamic programming approach.
the complexity for the algorithm is $\mathcal O(n^2)$ and the memory is $\mathcal O(n^2)$
First of all, precomuting the binomial coefficients takes time $ \mathcal O(n^2)$ using the pascal recurrence.
After this notice that in order to calculate $A_k$ we need to use $k$ operations, so the number of operations is $1+2+\dots+n=\frac{n(n+1)}{2}=\mathcal O(n^2)$
This algorithm can be easily modified to obtain an algorithm with time $\mathcal O(n^3)$ and memory $\mathcal O(n)$.to do we just need to change it so that the binomial coefficients are not precomputed. Instead calculate them when needed using the factorial formula.