Answer to Question #329697 in Algorithms for sandeep Lhs

Question #329697

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


1
Expert's answer
2022-04-17T07:41:06-0400

Recursion formula for binomial coefficient is nCk = n-1Ck-1 + n-1Ck

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(n2)



Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS