4 ms·
In "Algorithms" [Dasgupta, Papamdimitriou, Vazirani] they state that the memoization (e.g. querying a hash table) can have significant overhead leading to a lar
by reader5000 8y ago
In "Algorithms" [Dasgupta, Papamdimitriou, Vazirani] they state that the memoization (e.g. querying a hash table) can have significant overhead leading to a large constant factor in the big O analysis. On the other hand, the bottom up approach using a table solves all the possible subproblems including ones that are not needed and ones that the recursive approach would avoid. So from a big O perspective the recursive top-down and the table bottom-up approaches are the same but there can be significant constant factor differences.
- UncleMeat 8y agoThen mention this in the interview. I ask an algorithms question that would likely be hated on HN but when candidates tell me the practical difference (API cleanliness, maintainability, performance, extensibility) between approaches that ultimately don't impact asymptotic runtime I love it.
- baobabKoodaa 8y agoThis is true. However, both approaches are "dp" if we are talking about the equivalent solution implemented in these different ways.
- reader5000 8y agoYeah I thought the recursion+memo wasn't actually "dp" until I looked it up. Recursion without the memo is not DP however since you hit exp running time/memory and the whole point of DP is to avoid this.