CODEWITHSUNDEEP
arraysalgorithmdynamic-programmingcombinatoricsbinomial-coefficients
AbhinavChoudhury
AbhinavChoudhury

Reputation: 1187

Binomial coefficients using dynamic programming and one dimensional array

Most implementations of binomial coefficient computation using dynamic programming makes use of 2-dimensional arrays, as in these examples: http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2015%20-%20Dynamic%20Programming%20Binomial%20Coefficients.htm

http://www.geeksforgeeks.org/dynamic-programming-set-9-binomial-coefficient/

My question is, why not just compute it using a single dimensional array like this:

def C(n, r):
    memo = list()
    if (r > int(n/2)):
        r = n - r
    memo.append(1.0)
    for i in range(1,r+1):
        now = ((n-i+1)*memo[i-1])/i
        memo.append(now)
    return memo[r]

Basically using the recursive formula: C(n,r) = ((n-r+1)/r) * C(n,r-1)

This has a O(r) complexity, while the 2 dimensional logic has a O(nr) complexity.

Am I missing something here?

Upvotes: 0

Views: 795

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65427

If you want all of the values, then the 2D logic is certainly more efficient. The 2D logic may be more efficient for some parameters on some hardware that, e.g., lacks hardware multiply and divide. You have to be careful about integer overflow when multiplying before dividing, whereas the integer addition in the 2D recurrence is always fine. Other than that, no, the 1D recurrence is better.

Upvotes: 2

Related Questions