How to compute a two-variable recurrence function C(n,n) in O(n) time?

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
Post Reply
castrate
Posts: 27
Joined: Mon Aug 19, 2019 2:34 pm

How to compute a two-variable recurrence function C(n,n) in O(n) time?

Post by castrate »

Suppose we have a two-variable recurrence relation:
$C(n,k)=C(n-1,k)+C(n,k-1)$
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! :D
MuthuVeerappanR
Posts: 495
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: How to compute a two-variable recurrence function C(n,n) in O(n) time?

Post by MuthuVeerappanR »

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.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
pjt33
Posts: 70
Joined: Mon Oct 06, 2008 6:14 pm

Re: How to compute a two-variable recurrence function C(n,n) in O(n) time?

Post by pjt33 »

castrate wrote: Sun Dec 27, 2020 1:57 am Suppose we have a two-variable recurrence relation: $C(n,k)=C(n-1,k)+C(n,k-1)$ where boundary values such as $C(n,0)$ and $C(0,k)$ are given.
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 $n-i$ horizontal steps and $k-1$ vertical steps, so the contribution is $\binom{n-i+k-1}{n-i}$. 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.
Post Reply