Find Binomial Coefficient for 6C3 using dynamic programming approach and also explain in detail about complexity.
Recursion formula for binomial coefficient is nCk = n-1Ck-1 + n-1Ck
Algorithm:
The desired coefficient will be in C[6,3]
The external cycle in lines 3-6 is executed n-1 times, while the internal cycle in lines 5 and 6 is executed i times, that is 2, 3, ..., n times. So overall time complexity of the algorithm is O(n2)
Comments
Leave a comment