Answer to Question #329697 in Algorithms for sandeep Lhs

Question

Find Binomial Coefficient for 6C₃ using dynamic programming approach and also explain in detail about complexity.

Answer 1

Recursion formula for binomial coefficient is ⁿC_k = ^n-1C_k-1 + ^n-1C_k

Algorithm:

1. Set array C[1:n, 0:n] as a zero integer array
2. C[1,0]<-1, C[1,1]<-1
3. for i from 2 to n:
4. C[i,0] <- 1, C[i,i] <- 1
5. for j from 1 to i:
6. C[i,j] <- C[i-1, j-1] + C[i-1,j]

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(n²)