9
$\begingroup$

I have just completed a dynamic programming exercise on LeetCode (Coin Change). I tried a top down approach, but it failed for the larger inputs, whereas the bottom up approach worked for all inputs. Is the top down approach significantly slower because of the recursion?

I thought that bottom up approaches needed to compute everything: eg if we have a result array of size n, we run a loop from i=0 to i=n to find result[i], whereas the top down approach only computes relevant entries (we start at i=n then go down to 0, but we might skip some of the entries in between). So I thought the top down approach would be faster.

Or maybe there was just a bug in my top down approach.

Update: The problem on LeetCode is: " You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1: coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1)

Example 2: coins = [2], amount = 3 return -1."

I defined an array result of size amount+1; result[i] is the minimum number of coins needed to reach amount i (with result[0] = 0).

If we have N coins, and coin j has value V[j], the recursion is: result[i] = 1 + minimum of result[i-V[j]] for all j=1...N (only the j for which i-V[j]>=0)

I used a bottom up and top down approach to compute result[amount]:

If we don't have a coin of value 1, we won't need to compute result[i] for every i with a top down approach.

The time limit was exceeded for top down with this input: Coins: [186,419,83,408], Amount: 6249

$\endgroup$
4
  • 1
    $\begingroup$ What exactly are the algorithms you are implementing? What are the inputs? $\endgroup$
    – Raphael
    Dec 27, 2015 at 15:24
  • 3
    $\begingroup$ Top down can be faster if the relevant entries comprise a relatively small part of the output space, but it has some overhead compared to bottom up. If your problem is such that you need almost all the entries anyway, bottom up might be faster. You haven't really provided enough information to say anything more meaningful. $\endgroup$ Dec 27, 2015 at 15:46
  • 1
    $\begingroup$ Until we see your code I'll just bet on its being buggy. That's pretty much a safe bet all the time regarding any code. $\endgroup$ Aug 16, 2018 at 17:32
  • $\begingroup$ @AndrejBauer Exactly right. With the numbers involved, straightforward, unoptimised, but correct top-down approach should find the solution very, very quickly. $\endgroup$
    – gnasher729
    Oct 16, 2018 at 8:53

3 Answers 3

4
$\begingroup$

Top down approach would be faster in cases where the no of entries that you have to compute are significantly less than than the total number of entries. Remember, recursive approach is slow than iterative approach because there is some overhead of function call too.

Top down approach fails in some cases because it works by recursion. In recursion you require space (stack space) for storing each function call. Now, if the depth of your recursion tree is large you may run out of stack space. In that cases iterative approach (like bottom to top approach) works because you can use memory from heap and running out of stack space is not an issue there.

$\endgroup$
3
$\begingroup$

Top-down is usually slower because function calls and cache lookups are relatively expensive. Bottom-up is essentially filling a table, which is also more cache-friendly.

$\endgroup$
-1
$\begingroup$

What makes it slow isn't top down vs. bottom up. It will be slow if (a) you calculate the same intermediate result again and again, and (b) if you calculate results that in the end you don't need.

Typically top-down will tend to waste time by evaluating the same intermediate results again and again, unless you do something about it. And typically bottom-up will calculate intermediate results that you never need, unless you do something about it. Which is worse depends on the nature of the problem, and on your cleverness avoiding multiple or unnecessary evaluations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.