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

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.

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 .