Reduce Time Complexity -part 2

It is an undeniable fact that recursion is a powerful resource but, under certain circumstances it tends to produce overlapping subproblems, thereby increase the time complexity. Thus, it is wise to use Dynamic programming algorithms to counter the cons of recursion. Check out my blog on Dynamic Programming

Let's code the following problem from zero to hero!

Problem: Min Cost Path

Given an integer matrix of size m*n, you need to find out the value of minimum cost to reach from the cell (0, 0) to (m-1, n-1). From a cell (i, j), you can move in three directions : (i+1, j), (i, j+1) and (i+1, j+1). The cost of a path is defined as the sum of values of each cell through which path passes.

Sample Input 1 :
3 4
3 4 1 2
2 1 8 9
4 7 8 1
Sample Output 1 :
13

NOTE: Before writing the code I want you to think of a technique.

Brute-Force approach

To find the minimum cost to reach the end index, the aim is to find the minimum value at each step i.e. from the starting index add the value to the result and look for the minimum value amongst the adjacent indices which are - arr[i+1,j], arr[i+1,j+1] and arr[i,j+1] continue this until the last index is reached.

int helper(int **input,int m, int n , int i , int j)
{
    if(i == m || j == n)
    {
        return INT_MAX;
    }
    if(i == m-1 && j == n-1)
    {
        return input[i][j];
    }

    int a = helper(input,m,n,i+1,j+1);
    int b = helper(input,m,n,i,j+1);
    int c = helper(input,m,n,i+1,j);

    return input[i][j] + min(a,min(b,c));
}
int minCostPath(int **input, int m, int n) {
   return helper(input,m,n,0,0); // helper function for indices i,j.
}

Time Complexity

The time complexity computation is simple at each point there are three recursive calls, Thus, the total number of calls made = 3^x, where x = max(m,n). Therefore, the time complexity of this solution is :

        Time complexity T(n) = O(3^x), where x = max(m,n) //Very Bad

The time complexity is apparently very bad, thus, to improve the time complexity it is necessary to understand the analysis of the algorithms. As we already know, the recursive approach deals with intermediate subproblems, thus to overcome this hitch, we'll store the results of the overlapping subproblems with the Dynamic Programming algorithm.

Dynamic programming

The idea behind any dynamic Programming algorithm is to look for the independent factors in the solution and find the solution for all the dependent instances until the desired result is found. To understand the concept of Dynamic Programming check out my Blog.

To find the minimum cost of traversal we'll follow the bottom-up approach, starting from the last index reaching the first would include the total cost of traversal. Starting from the end index store the minimum adjacent value at every index i.e. minimum of arr[i+1,j], arr[i+1,j+1] and arr[i,j+1], reaching to the start index.

int minCostPath(int **input, int m, int n) {
   int **arr = new int*[m];
    for(int i = 0; i < n; i++) {
        arr[i] = new int[n];
    }
    //Fill last
    arr[m-1][n-1]= input[m-1][n-1];
    for(int i = n-2;i>=0;i--)
    {
        arr[m-1][i]= arr[m-1][i+1]+input[m-1][i];
    }
    for(int i = m-2;i>=0;i--)
    {
        arr[i][n-1] = input[i][n-1]+arr[i+1][n-1];
    }

    for(int i = m-2;i>=0;i--)
    {
        for(int j = n-2;j>=0;j--)
        {
            arr[i][j] = min(arr[i][j+1],min(arr[i+1][j],arr[i+1][j+1]))+input[i][j];
        }
    }
    return arr[0][0];
}

Time Complexity

The time complexity of the approach is same as that of traversing a 2D array. But, in this approach, there is an involvement of extra space for storing intermediate results, which gives rise to space complexity.

Time Complexity: O(m*n) //better than recurssive aproach
Space Complexity: O(m*n)//Extra Memory

It is evident that there is an interpose of space complexity but that is ignorable.

CONCLUSION

Time complexity T(n) DP <<  Time complexity T(n) Recursive Approach

Therefore, while dealing with recursion think back & store the results of redundant subproblems to reduce the overall time complexity.

For complete code visit here

Thank you,

Shreya Sharma

#Recursion

#DynamicProgramming

#DataStructures