Memoziation vs Tabulation

1

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

2

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

3

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[0] = 1;
for(int i = 1; i <= (1e6); i++)
    fact[i] = (fact[i-1] * i) % p;
// Overhead in calculation
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
4

Okay.
So what should we prefer ?

5

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.

6

Okay . Great.
Thanks for helping me out.

1 Like
7

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.

8

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 .