to calculate current row we need to parse previous row. In this way it creates pattern of AP arithmetic progression… 1 + 2 + 3 + … n
Therefore, resulting time complexity should be O(n^2) instead of O(n)
Course: https://www.educative.io/collection/10370001/5347133077061632
Lesson: https://www.educative.io/collection/page/10370001/5347133077061632/6248391839318016
The time complexity of the recursive implementation of Pascal’s triangle is indeed O(n), not O(n^2). Although it may seem that we are iterating through the previous row to calculate each element in the current row, it’s important to note that we’re not recalculating the entire previous row for each element. Instead, we’re using the values computed in the previous row directly to calculate the values in the current row.
Each element in the current row is the sum of two elements from the previous row. So, for each row, we perform a fixed number of additions (equal to the number of elements in the row), which results in a linear time complexity relative to the number of rows, hence O(n), where n is the number of rows in the triangle.
While it might resemble an arithmetic progression due to the nature of how the values are summed up, the overall time complexity is still linear because we’re not iterating through the entire triangle for each row.
If you were to consider an iterative approach, where you explicitly calculate each element of each row, then yes, the time complexity would indeed be O(n^2). However, the provided recursive implementation leverages the previous row’s values efficiently, leading to a more optimal time complexity of O(n).
If you have any further questions or need additional clarification, feel free to ask!