Space=O(n*k) Time=O(n*k)

space complexity is just the extra space you need.

To compute the binomial coefficient we use a 2-D matrix of size n*k..

Thus we use extra space of order n*k

and then use recursive definition of binomial coefficients

ie C(n,k)=C(n-1,k)+C(n-1,k-1)

To compute the binomial coefficient we use a 2-D matrix of size n*k..

Thus we use extra space of order n*k

and then use recursive definition of binomial coefficients

ie C(n,k)=C(n-1,k)+C(n-1,k-1)

## No comments:

## Post a Comment

Note: Only a member of this blog may post a comment.