As with the Fibonacci numbers, the binomial coefficients can be calculated recursively - making use of the relation:

^{n}C

_{m}=

^{n-1}C

_{m-1}+

^{n-1}C

_{m}

However, we all know that if we construct Pascal's triangle, the

**row gives all the values,***n*^{th}^{n}C_{m}, m = 0,n:```
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
``` |

**time to calculate and there are**

*O(*1*)***of them. So this calculation of the coefficients takes**

*O(n*^{2}*)***time. But it uses**

*O(n*^{2}*)***space to store the coefficients.**

*O(n*^{2}*)*