educative.io

Educative

Pascal triangle

How Pascal trigle is considered to be a divide and conquer algorithm ?
What are the divide, conquer, merge steps ?

Although I have the same confusion, I think we could try to think the divide and conquer as:
(1)divide: split the question to smaller size (recursively)
(2)conquer: solve the smallest version of problem( first row of the triagle)
(3)merge: use the smaller version result to build bigger result( calc next row based on current row)

However, I think the Time complexity is not O(n), because eventually we calculated all the numbers in the triangle. which is 0.5n^2 numbers. the time complexity should be O(n^2).

1 Like