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 '13 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$ – Joseph Stack Dec 23 '13 at 14:09

Your Answer

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

Browse other questions tagged or ask your own question.