Where to use Memoization?
We can use the memoization technique where the use of the previously-calculated results comes into the picture. This kind of problem is mostly used in the context of recursion, especially with problems that involve overlapping subproblems.
Let’s take an example where the same subproblem repeats again and again.
Example to show where to use memoization:
Let us try to find the factorial of a number.
Below is a recursive method for finding the factorial of a number:
int factorial(unsigned int n)
{
if (n == 0)
return 1;
return n * factorial(n – 1);
}
What happens if we use this recursive method?
If you write the complete code for the above snippet, you will notice that there will be 2 methods in the code:
1. factorial(n)
2. main()
Now if we have multiple queries to find the factorial, such as finding factorial of 2, 3, 9, and 5, then we will need to call the factorial() method 4 times:
factorial(2)
factorial(3)
factorial(9)
factorial(5)
Recursive method to find Factorial
So it is safe to say that for finding factorial of numbers K numbers, the time complexity needed will be O(N*K)
- O(N) to find the factorial of a particular number, and
- O(K) to call the factorial() method K different times.
How Memoization can help with such problems?
If we notice in the above problem, while calculation factorial of 9:
- We are calculating the factorial of 2
- We are also calculating the factorial of 3,
- and We are calculating the factorial of 5 as well
Therefore if we store the result of each individual factorial at the first time of calculation, we can easily return the factorial of any required number in just O(1) time. This process is known as Memoization.
Solution using Memoization (How does memoization work?):
If we find the factorial of 9 first and store the results of individual sub-problems, we can easily print the factorial of each input in O(1).
Therefore the time complexity to find factorial numbers using memoization will be O(N)
- O(N) to find the factorial of the largest input
- O(1) to print the factorial of each input.
What is memoization? A Complete tutorial
The term “Memoization” comes from the Latin word “memorandum” (to remember), which is commonly shortened to “memo” in American English, and which means “to transform the results of a function into something to remember.”.
In computing, memoization is used to speed up computer programs by eliminating the repetitive computation of results, and by avoiding repeated calls to functions that process the same input.
What is memoization
Table of Contents
- What is Memoization?
- Why is Memoization used>
- Where to use Memoization?
- Types of Memoization
- How Memoization Technique used in Dynamic Programming?
- Top Down Approach
- Bottom Up Approach
- How Memoization is different from Tabulation?
- Coding Practice Problems for Memoization
- FAQs
- 1) Is memoization better than DP?
- 2) Is memoization the same as caching?
- 3) Why memoization is top down?
- 4) Does memoization use recursion?
- 5) Should I use tabulation or memoization?
- 6) Where is memoization used?
- 7) Why is it called memoization?
- 8) How does memoization reduce time complexity?
- 9) What is difference between memoization and caching?
- 10) Why tabulation is faster than memoization?
- Conclusion
Contact Us