Is Bottom-up DP solution better than Top-down in terms of Time complexity?

Question

Are there any Dynamic Programming Problems where the Bottom-Up solution has better time complexity than Top-Down (Memoization) solution?

Answer 1

Asymptotically both DP and Memoization give the same Time Complexity. However, at run-time, the DP solution outpaces Memoization technique by some constant factor.
This is because of the fact that in the case of DP we just need to look into the table for results of sub-problems while in case of Memoization we need to call recursion and then it returns the result whether by directly checking into hashtable/array(whatever you used) if its already computed or by computing it, which in turn consumes more CPU cycle.

In some cases, it might happen that our sub-problem space is very large but we do not require all sub-problems to get our answer then, Memoization could be lucrative because it solves only inevitable problems instead of all. But, this case is very seldom to occur because Many a time we optimise our DP code only in such a way that it doesn't iterate for all sub-problems instead only for required sub-problems.

Hence, generally speaking, Bottom-Up approach i.e., DP solution always runs faster than its corresponding Memoization solution.

Note: I'm using the word runs faster instead of time complexity because time complexity is asymptotic which is same for both.