why is it o(n)? you can store the value for each combination only if it’s bigger than the current value that way it’ll be O(1)
Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Solution: 0/1 Knapsack
1 Like
Hello @Soroush_Bassam,
Each recursive call to find_max_knapsack_profit_helper adds a frame to the call stack, and the maximum depth of the call stack is equal to the number of items (n). In the worst case, the algorithm may have to explore all possible combinations of including or excluding each item, leading to a maximum call stack depth of n.
Therefore, the space complexity is O(n), as the space required for the call stack is proportional to the number of items in the knapsack problem.
I hope this answers your query regarding the space complexity of the naive approach. Please feel free to share more feedback and suggestions. We’d be happy to help. Thanks!
Happy learning!
1 Like