Suppose we have a twovariable recurrence relation:
$C(n,k)=C(n1,k)+C(n,k1)$
where boundary values such as $C(n,0)$ and $C(0,k)$ are given.
Our target is to find $C(n,n)$.
A simple DP algorithm could solve it, but in $O(n^2)$ time, which is not capable of large values of n ($10^7$ or higher).
So is there any way to compute $C(n,n)$ in linear time?
Any help would be appreciated!
How to compute a twovariable recurrence function C(n,n) in O(n) time?

 Posts: 495
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Re: How to compute a twovariable recurrence function C(n,n) in O(n) time?
A simple idea is to convert them into bivariate generating functions.. For example, define
$\displaystyle F(x, y) = \sum_{n,k \geq 0}C(n,k)x^ny^k$
Use the recurrence you have quoted to arrive at an expression for $F(x,y)$. That should hopefully give you the required $O(n)$ algo.
$\displaystyle F(x, y) = \sum_{n,k \geq 0}C(n,k)x^ny^k$
Use the recurrence you have quoted to arrive at an expression for $F(x,y)$. That should hopefully give you the required $O(n)$ algo.
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
Re: How to compute a twovariable recurrence function C(n,n) in O(n) time?
For this specific example, first note that only addition is involved so the contributions of the $C(i,0)$ and $C(0,j)$ are independent. Then consider the paths from wlog $(i,0)$ to $(n,k)$. The first step has to be down, to $(i,1)$; then there are $ni$ horizontal steps and $k1$ vertical steps, so the contribution is $\binom{ni+k1}{ni}$. Similarly for $(0,j)$, and you get $C(n,k)$ as a pair of sums, each weighted by binomial coefficients. I assume that you can take it from there, because sums weighted by binomial coefficients which need to be evaluated in linear time come up a lot in Project Euler.