Grokking Algorithm Complexity and Big-O
Ask Author
Back to course home

0% completed

Vote For New Content
Dynamic Programming Algorithms
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

In this lesson, we will explore three different approaches to solving dynamic programming problems with more complex examples:

  • Memoization (Top-down approach)
  • Top-down DP with Explicit Recursion
  • Bottom-up DP (Tabulation)

1. Solving a Problem with Memoization

Problem: Calculate the number of unique paths from the top-left corner to the bottom-right corner of an m x n grid. You can only move right or down.

Python3
Python3
. . . .

Time Complexity for Unique Paths Using Memoization

  1. Recursive Calls:
    • The function findPaths is called recursively to compute the number of unique paths to each cell in the m x n grid.
    • Number of Unique States: Each state is defined by a unique (row, col) combination, and there are O(m \cdot n) such unique states in the grid.
    • Number of Recursive Calls:
      • Each unique state is computed only once, as we use memoization. This prevents redundant recursive calls and ensures each state is solved once.
    • Overall Time Complexity: O(m \cdot n)

Space Complexity for Unique Paths Using Memoization

  1. Memoization Map (memo):

    • The memo map stores results for each unique state (row, col), so it has space complexity O(m \cdot n).
    • The size of the String keys is insignificant compared to the number of entries, so this does not impact the space complexity significantly.

  2. Recursive Call Stack:

    • Maximum Depth:
      • The maximum depth of the recursive call stack is O(m + n) in the worst case, representing the diagonal traversal of the grid from (m-1, n-1) to (0, 0).

  3. Overall Space Complexity:

    • The total space complexity accounts for both the memoization map and the call stack depth: O(m \cdot n), for storing results, plus O(m + n) for the recursion stack.

2. Solving a Problem with Top-Down DP

Problem: Calculate the minimum cost to climb a staircase where each step has a certain cost associated with it. You can climb one or two steps at a time.

Python3
Python3
. . . .

Time Complexity for Minimum Cost Climbing Stairs Using Top-Down DP

  1. Recursive Calls:
    • The function findMinCost is called recursively to compute the minimum cost for each step i.
    • Number of Unique Subproblems:
      • Each index from 0 to n-1 (where n is the length of the cost array) represents a unique subproblem.
      • Since each subproblem is computed only once due to memoization, the total number of recursive calls is O(n).
  2. Key Operations:
    • Base Case Checks:
      • The checks if (i < 0), if (i == 0 || i == 1), and if (dp[i] != -1) run in O(1).
    • Recursive Calculations:
      • For each call to findMinCost, two recursive calls are made (findMinCost(cost, i - 1) and findMinCost(cost, i - 2)), but due to memoization, each index is only processed once.
    • Filling and Returning Values:
      • Storing and returning values in dp[i] take O(1).

Overall Time Complexity:

  • Each index i from 0 to n-1 is processed once, leading to a total time complexity of: O(n)

Space Complexity for Minimum Cost Climbing Stairs Using Top-Down DP

  1. DP Array (dp):

    • The dp array is used to store precomputed results for each index from 0 to n-1, taking O(n) space.

  2. Recursive Call Stack:

    • Maximum Depth of Recursion:
      • The maximum depth of the recursion is O(n), which occurs when the function is called starting from the highest index down to 0.
    • Space Complexity for Call Stack: O(n)

    The space used by the recursion stack can go up to O(n) in the worst case.

3. Solving a Problem with Bottom-Up DP

Problem: Find the length of the longest palindromic subsequence in a given string.

Python3
Python3
. . . .

Time Complexity for Longest Palindromic Subsequence Using Bottom-Up DP

  1. Initialization:

    • Single Character Initialization:
      • The for loop that sets dp[i][i] = 1 for each i runs O(n) times, where n is the length of the input string s.

  2. Nested Loops:

    • The outer loop runs O(n) times, as it iterates over lengths of substrings starting from 2 up to n.
    • The middle loop runs O(n) times for each length, as it starts from the beginning of the string up to n - len.
    • The inner loop computes the value at dp[i][j], where j = i + len - 1, and runs O(1) operations for each combination.

  3. Overall Time Complexity:

    • The number of operations for filling the dp table is O(n^2) because each of the n(n-1)/2 cells in the upper triangle of the 2D array is filled once.
    • Total Time Complexity: O(n^2)

Space Complexity for Longest Palindromic Subsequence Using Bottom-Up DP

  1. DP Table (dp):

    • The 2D dp table has a size of n \times n, where n is the length of the input string s.
    • Space used by dp: O(n^2)

  2. Auxiliary Space:

    • The algorithm does not use any additional data structures that grow with the input size.
    • Overall auxiliary space: O(1).

Overall Space Complexity:

  • The total space complexity is: O(n^2)

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible