# Memoziation vs Tabulation

is there any difference in Time Complexity of memozied and tabulation method of a problem?
Thanks!!

I think Tabulation is faster since it accesses data directly from the table. Memoization, on the other hand, uses recursion calls which are slow.

When it comes to Tabulation, Tabulation has fixed time complexity. It doesn’t depend on number of test cases. Let there be 10 test cases or 10^6 test cases, time taken for Tabulation remains the same. Time complexity = O(K + T) where K is the constant time taken for tabulation and T is the number of test cases.

For Memoization, the values will be calculated on demand. There is no overhead as it was in Tabulation.

Example:

Consider an example where you are supposed to calculate N factorial mod p for several test cases.
Constraints:
1 \le T \le 10^6
1 \le N \le 10^6
P = 10^9 + 7

Tabulation:

``````fact = 1;
for(int i = 1; i <= (1e6); i++)
fact[i] = (fact[i-1] * i) % p;
cin >> t;
while(t--) {
int n;
cin >> n;
cout << fact[n] << endl;
}
``````

Memoization:

``````ll fact[maxN];
ll mod = ((ll)(1e9+7));

void get(int n) {
if(n == 0) {
return 1;
}
else if(!fact[n]) {
return fact[n] = (get(n-1) * n) % (mod);
}
return fact[n];
}

int main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
cout << get(n) << endl;
}
}
``````

Example Test Case where Memoization is better than Tabulation:

``````3
10
20
15
``````

PS: Ignore the compilation errors. These are just code snippets.

3 Likes

Okay.
So what should we prefer ?

It is problem specific. If there are too many test cases, say around 10^6, tabulation is preferred.
But it doesn’t make much difference in the execution time. Memoization gives the actual power to DP though.

Okay . Great.
Thanks for helping me out.

1 Like

Hey, I just recollected that there is a problem titled “Bytelandian Gold Coins”. I think Tabulation will not work here. Memoization is used to solve this problem.

yes.
Here tabulation will not work because in worst case n is 10^9 .
And we cannot make such a large array.(If you think other reason, please tell me)
So, memoization is preferred here.

Good question to distinguish between tabulation and memoization.
Thanks .