Tabulation vs Memoization

What is memoization (Top-down Dynamic Programming)? 

Memoization technique or top-down approach is implemented in DP algorithms where the highest-level sub-problems are solved first. Initially, it solves the highest-level subproblem and then solve the next sub-problem recursively and the next. Suppose there are two sub-problems, i.e., sub-problem A and sub-problem B. When sub-problem B is called recursively, then it can use the solution of sub-problem A, which has already been used.  Memoization saves time by avoiding solving the entire recursion tree generated by some problem with overlapping subproblems because the first problem and its sub-problems are memoized already.

Difference Between Tabulation and Memoization

Comparison of working of Memoization and Tabulation with an example

In a Fibonacci sequence, the sum of two preceding numbers is the next number in the sequence. Eg: 0, 1, 1, 2, 3, 5, 8, 13…

The three conditions for a Fibonacci sequence are:

• If n = 0, F(n) = 0 
• If n = 1, F(n)=1
• If n > 1, F(n) = F(n - 1) + f(n - 2)

Tabulation or bottom-up approach:

To find f(5) in the series 0,1,1,2,3,5...., a total of 15 calls will be needed.

Source:Javatpoint

Memoization or top-down approach:

To go from the source ‘0’ to destination ‘5’, it can either be navigated through vertex ‘2’ or ‘3’. Assuming the distance between vertices ‘0’ and ‘2’ is 1 and the distance between ‘0’ and ‘3’ is 2, the decision will be made depending on the minimum distance possible.

Considering vertex ‘2’, the distance between 0 and 5 will be 1 + 1 = 2;

Considering vertex ‘3’, the distance between 0 and 5 will be 2 + 1 = 3

Since the minimum possible distance is ‘2’, we will consider vertex 2 for the operation. This will reduce the time complexity of the operation.

Source:Javatpoint

Recursive code with no-cache, for a Fibonacci problem:

public class fibRecursive
{  
    int fibonacci(int i)
    {
        if (i < 2)
          return i;
        return fibonacci(i-1) + fibonacci(i-2);
    }

    public static void main(String[] args)
    {
        System.out.println(new fibRecursive().fibonacci(10));
    }
}

Output

Memoization Algorithm

• This technique will require a function for cache, which is named ‘fibMemoization’ in the given snippet.
• Next, for the Fibonacci series, a function named ‘fibonacci’ is created where a number is taken as input and checked for 0 or 1, in which cases cache[n]=n. For other cases, cache[n] will be calculated by calling the function within itself, i.e., cache[n] = fibonacci( n - 1 ) + fibonacci( n - 2)
• cache[n] is returned, and the main function is written to print the output.

Code snippet for memoization:

public class fibMemoization
{  
    int[] cache;

    fibMemoization(int[] cache)
    {
        this.cache = cache;
    }

    int fibonacci(int n)
    {
        if (cache[n] == 0)
        {
            if (n < 2)
              cache[n] = n;
            else
              cache[n] = fibonacci(n-1) + fibonacci( n-2);
        }

        return cache[n];
    }

    public static void main(String[] args)
    {
        int n = 10;
        System.out.println(new fibMemoization(new int[n+1]).fibonacci(n));
    }
}

Output

Time Complexity

The cache is checked to see if there’s already an answer stored in the nth spot and is returned if there. Otherwise, the sum of fibonacci(N - 1) and fibonacci(N - 2) is called recursively, and the sum is set to a variable. This sum is placed in the cache array at the ‘N’th spot, and then the value of the sum is returned. With this solution in memoization, whenever fibonacci(N) is called, and ‘N’ has already been solved once, cache[n] will already hold the answer and return it. The time complexity from recursively calling fibonacci(N - 1) + fibonacci(N - 2) is O(2 ^ N) and becomes a lot better with memoization - O(N).

Space Complexity

Using the memoization technique, each ‘fibonacci’ value will be calculated only once. So, the space complexity will be O(N), where ‘N’ is the input number to ‘fibonacci’ (the array for memoization will hold ‘N’ numbers).

Read More - Time Complexity of Sorting Algorithms

Tabulation Algorithm

• An integer function is created to take input ‘N’ and create the array for the cache.
• The cache array is initialized for elements ‘0’ and ‘1’. 
• Other elements of the Fibonacci series are stored in the cache using a for-loop.
• Finally, after cache[n] is returned, the main function to print output is written

Code snippet for tabulation:

public class fibTabular
{  
    int fibonacci(int n)
    {
        int[] cache = new int[n+1];
        cache[0] = 0;
        cache[1] = 1;

        for (int i = 2; i <= n; i++)
        {
            cache[i] = cache[i-1] + cache[i-2];
        }

        return cache[n];
    }

    public static void main(String[] args)
    {
        System.out.println(new FibonacciTabular().fibonacci(10));
    }
}

Output

Time Complexity

The loop is run as long as ‘i’ is less than or equal to ‘N’ to reach the ‘N’th value correctly. The loop is iterated, and ‘i’ is incremented each time instead of recursively breaking down. This ensures that no value is recomputed and the current value is returned in O(N) time.

Space Complexity

Since tabulation or the bottoms-up approach used constant space, the space complexity for this algorithm would be O(1).

Frequently Asked Questions

Is tabulation always better than memoization?

If all subproblems need to be solved in the given problem, tabulation mostly outperforms memoization since it has no overhead for recursion. The tabulation technique can use a preallocated array instead of a hash map.

What is the disadvantage of memoization?

Some of the disadvantages of memoization are space overhead, slow initial execution, and extra burden on programmers as they might need to modify the code.

How do table entries work differently in tabulation and memoization?

Entries are filled one by one in a tabulated version, while entries are filled on-demand in the memoized version.

Conclusion

In this article, we learned the difference between the tabulation and memoization techniques and how differently they are implemented, along with examples.

You can go to Coding Ninjas Studio and try solving problems. Share this blog with your friends if you found it helpful!
Recommended Reading:

Difference Between Analog and Digital Computer

Until then, All the best for your future endeavors, and Keep Coding.