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