Wednesday, April 1, 2009

Dynamic Programming: what is the space and time complexity of a dynamic programing algo for calulating the binomial coefficient C(n,k)

The Answer Is Simple
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)

No comments:

Post a Comment

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