Sunday, November 25, 2012

Pascal’s triangle is a triangular array of the binomial coefficients

Method 1 -
Each line n is the binomial coefficient C(n, k) where k is the row. This has complexity n^3. because in this case k has the same order of n

Method 2
Complexity n^2, with space n^2

Method 3
complexity n^2, with space O(1) -- this is more difficult because you need to move in the triangle storing just a constant number of locations. Can you express C(n, k) as function of C(n, k-1)?

No comments:

Post a Comment