Skip to content

Latest commit

 

History

History
19 lines (10 loc) · 1.55 KB

complexity.md

File metadata and controls

19 lines (10 loc) · 1.55 KB

Time Complexity (Big O Time):

  1. The program uses dynamic programming to fill in a 2D array dm of size mxn, where 'm' is the number of rows and 'n' is the number of columns in the grid.

  2. The first two loops (one for the last row and one for the last column) each run in O(max(m, n)) time because they iterate through the entire last row and last column.

  3. The recur method is called recursively for each cell in the grid, but it uses memoization (dm array) to avoid redundant calculations. In the worst case, it recursively computes the minimum path sum for all cells in the grid.

  4. Therefore, the overall time complexity of the program is O(m * n), where 'm' is the number of rows, and 'n' is the number of columns in the grid.

Space Complexity (Big O Space):

  1. The program uses a 2D array dm of size mxn to store the intermediate results. Therefore, the space complexity is O(m * n), where 'm' is the number of rows, and 'n' is the number of columns in the grid.

  2. The space complexity is dominated by the dm array, and it does not depend on the input values of 'm' and 'n' but only on the grid size.

  3. Additionally, the program uses some integer variables and constants, but their space usage is constant and does not depend on the grid size.

In summary, the time complexity of the provided program is O(m * n), and the space complexity is also O(m * n), where 'm' is the number of rows, and 'n' is the number of columns in the grid. The program efficiently calculates the minimum path sum in the grid using dynamic programming with memoization.