Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is tabulation (Bottom-Up Dynamic Programming)?
3.
What is memoization (Top-down Dynamic Programming)?
4.
Difference Between Tabulation and Memoization
5.
Comparison of working of Memoization and Tabulation with an example
5.1.
Tabulation or bottom-up approach:
5.2.
Memoization or top-down approach:
5.3.
Output
6.
Memoization Algorithm
6.1.
Code snippet for memoization:
6.2.
Output
6.3.
Time Complexity
6.4.
Space Complexity
7.
Tabulation Algorithm
7.1.
Code snippet for tabulation:
7.2.
Output
7.3.
Time Complexity
7.4.
Space Complexity
8.
Frequently Asked Questions
8.1.
Is tabulation always better than memoization?
8.2.
What is the disadvantage of memoization?
9.
How do table entries work differently in tabulation and memoization?
10.
Conclusion
Last Updated: Apr 29, 2024
Easy

# Tabulation vs Memoization

Reet Maggo
3 upvotes
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
Earn badges and level up

## Introduction

Dynamic programming is used to solve recursive problems iteratively and is applicable for overlapping subproblems. Problems are resolved by breaking them down into smaller subproblems and caching the overlapping subproblems to be reused to save time later. DP is usually implemented through tabulation but can also be done using memoization.

In this blog, we have also used an example and its code snippet for tabulation and memoization techniques to understand the concept better.

## What is tabulation (Bottom-Up Dynamic Programming)?

The tabulation technique or the bottom-up approach is implemented in DP algorithms where the lowest level sub-problem are solved first. In these cases, the solution to the lowest level problem helps solve the next level problem, and so on. All the sub-problems are solved iteratively in this manner till the end. Tabulation saves a lot of time when a sub-problem needs the solution from a problem that has already been solved before.

You can also learn about C Programming Language here

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## 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.

## 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));
}
}``````

## 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));
}
}``````

### 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));
}
}``````

### 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.

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
Earn badges and level up
Live masterclass