Our input is a $(n+1)\times (n+1)$ table filled with some value (integer) for each leftmost and bottom cell $l_i,b_i$ as in the figure. We wish to compute the value of all upper and rightmost cells $u_i$ and $r_i$ ($1\leq i\leq n$) when each cell of the table is filled recursively according to the equation $T(x,y)=T(x,y-1)+T(x-1,y)$ for each $x,y\geq 1$. picture to illustrate problem input

If we compute naively the $u_i,r_i$ by filling the table, or summing corresponding binomial coefficients, the complexity is $\Theta(n^2)$. Is this a lower bound for the problem or is there any way to compute all $u_i, r_i$ in $o(n^2)$? If so, does the technique extend to rectangular tables?

  • 1
    $\begingroup$ You can assume that you have just the upper left triangle and the values are on the diagonal without loss of generality. So this question is essentially the same problem as computing $$\sum_{0 \leq i \leq n} {n \choose i} a_i$$ $\endgroup$
    – Kaveh
    Dec 19, 2013 at 21:02
  • $\begingroup$ @kaveh: Thanks. I suppose that the 'upper left triangle' means: we can consider independently the contribution originating from the $b_i$ and those from the $l_i$. Then indeed we only need to compute $O(n)$ sums of $O(n)$ binomial coefficients (I actually hinted at this in the question: 'summing binomial coefficients'). However, I do not see how to compute $\sum_{0 \leq i \leq j} {j \choose i} a_i$ for all $j\in \{1,...,n\}$ in $o(n^2)$. Maybe this is because I did not understand the part about 'values are on the diagonal'? $\endgroup$ Dec 23, 2013 at 14:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.