Two things to consider when deciding which algorithm to use
- Time Complexity. Both approaches have the same time complexity in general, but because for loop is cheaper than recursive function calls, bottom-up can be faster if measured in machine time.
- Space Complexity. (without considering extra call stack allocations during top-down) Usually both approaches need to build a table for all sub-solutions, but bottom-up is following a topological order, its cost of auxiliary space can be sometimes reduced to the size of problem’s immediate dependencies. For example:
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
, we only need to store the past two calculations
That being said, bottom-up is not always the best choice, I will try to illustrate with examples:
- Top-down only solves sub-problems used by your solution whereas bottom-up might waste time on redundant sub-problems. A silly example would be 0-1 knapsack with 1 item…run time difference is
O(1)
vsO(weight)
- you might need to perform extra work to get topological order for bottm-up. In Longest Increasing Path in Matrix if we want to do sub-problems after their dependencies, we would have to sort all entries of the matrix in descending order, that’s extra
nmlog(nm)
pre-processing time before DP