0
$\begingroup$

For cases where recursion is used as well as memoization (so that a number of subtrees of what would otherwise be the overall recursive call tree are each replaced to be O(1)), I am wondering what the resulting runtime is (such as whether it is the same as the corresponding dynamic programming approach), or really, how to calculate it if it is not the same as the corresponding dynamic programming approach?

Example: I am wondering, for this leetcode problem, what the runtime of the following solution would be (courtesy of this solution):

    unordered_map<string, int> memo;
    int profit(vector<int>& prices, int i, int isBuy, int k){
        if(i == prices.size() || k == 2)     // return if two transactions are completed
            return 0;
        string key = to_string(i) + "-" + to_string(isBuy) + "-" + to_string(k);
        if(memo.find(key)!=memo.end())
            return memo[key];
        int a,b;
        if(isBuy){                           // if isBuy is 1, we have a choice to purchase the stock
            a = profit(prices, i + 1, 1, k);                       // do not buy
            b = profit(prices, i + 1, 0, k) - prices[i];           // buy and add the cost 
        }  
        else{                                // if isBuy is 0, we can only sell as we have already bought
            a = profit(prices, i + 1, 0, k);                       // do not sell
            b = profit(prices, i + 1, 1, k + 1) + prices[i];       // sell and add the profit
        }   
        return memo[key] = max(a, b);        // best choice among trading and skipping
    }
    
    int maxProfit(vector<int>& prices) {
        return profit(prices, 0, 1, 0);
    }

For instance, is the runtime here O(n * 2 * k) = O(nk) here, where n = prices.size(), 2 for whether is a buy or sell, and k for the number of possible times we can buy or sell (I know it's 2 here, so really O(n) overall)?

My question is mainly because recursion with memoization, though it may make a certain subtree of recursive calls become O(1), still can have that subtree occur multiple times in the overall recursive tree of calls; and so I'm wondering if this memoization with the recursion really succeeds in bringing the runtime down to what it would be with dynamic programming (ie just arrays/vectors and loops, without recursion), or if because each of those now-O(1) subtree recursive call roots can occur multiple times, it's actually greater than that?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Please explain the leetcode problem concisely here, instead of only linking to it. Write the solution(s) using your own words and/or concise pseudocode, instead of C++ code which we do not accept here in computer science SE. Explain why do you believe recursion and memoization is different from dynamic programming, since this is exactly how most textbooks define dynamic programming. My preliminary view is that it is indeed $O(n)$, which leads to a programming question answerable by self debugging or in Stack Overflow about bugs in the program, or just that recursion is slower than iteration. $\endgroup$ Commented Jan 28, 2024 at 9:19
  • $\begingroup$ According to the comments section and other solutions, there are many accepted recursion solutions, you may read through them. $\endgroup$ Commented Jan 28, 2024 at 9:41

0

Reset to default

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.