Sommaire |
Pascal triangle can be used to calculate number of combinations using the recursion formula below:-
(n k) = (n-1 k-1) + (n-1 k)
This can be used in place of formal expansion of (n k) to calculate number of combinations. But both perform in O(n) time.What are the advantages of using Pascal s triangle method?
The main advantage lies in the fact that you can pre-compute all (ni ki) where ni < n and ki <= k in O(n^2) time.
So if you have a problem where you may need to query different values in a Pascal triangle, using the recursion formula method and storing all sub-results will mean your preprocessing time is O(n^2) but your queries are O(1).
On the other hand, using the formula for (n k) in the same application would mean each query is O(n) which is inferior to the former approach if you expect more than n queries.
License : cc by-sa 3.0
http://stackoverflow.com/questions/23732886/pascals-triangle-advantages
