CODEWITHSUNDEEP
pythonrecursiontreebig-oternary-tree
Rodrigo
Rodrigo

Reputation: 133

Big O complexity of creating a recursive ternary tree with k width

I want to know the complexity of my algorithm.

I'm trying to optimize the profit of buying stocks at every leaf of a tree from a list of prices. For every price we can do 3 options, buy one unit, sell one unit or do nothing. There is a constraint which bounds the amount of stocks we can have at a time, like 0 stocks min and 5 stocks max so if we have a list of 20 prices, which actions should I take to maximize the profit and end with 3 stocks.

For this task I created this recursive method:

    def _next_price_unit(self, load, prices, money=0, depth=0):
"""Recursive dynamic programming step
            Tree load has a depth index where the max depth is the length of the
            prices array while load index is the level of current stocks.The
            tree load will return the best revenue at that depth and stock load."""

        if len(prices) is depth:  # Max depth, stop condition
            return
        if self.tree_load[depth][load] < money:  # No change in load
            self.tree_load[depth][load] = money
            self._next_price_unit(load, prices, money, depth + 1)

         #Check load in stock boundaries and money increases at -1 or +1 load
        if load - 1 >= self.stock_min\
                and money + prices[depth] > self.tree_load[depth][load - 1]:
            self.tree_load[depth][load - 1] = money + prices[depth]  # Sell
            self._next_price_unit(load - 1, prices, money + prices[depth],
                                  depth + 1)

        if load+1 <= self.stock_max\
                and money - prices[depth] > self.tree_load[depth][load+1]:
            self.tree_load[depth][load + 1] = money - prices[depth]  # Buy
            self._next_price_unit(load + 1, prices, money - prices[depth],
                                  depth + 1)

Without the constraint of min and max stock I know the complexity of a ternary tree would be O(3^n) and I know this could be solved in O(k*n) if I use dynamic programming comparing the values at each level of depth and then going forward. This algorithm will go all the way to the depth end, then backwards, forwards,backwards backwards and so on.

Can someone tell me what is the complexity? I cant get my head around it.

Upvotes: 1

Views: 92

Answers (0)

Related Questions