I need help visualising the recursive tree for Minimum Coins needed problem, where we have to find out the minimum number of coins required to make a Value.
I can’t figure out the time complexity of this problem, I think it should be the level^n. (Where level is the level of value until it reaches less than or equal to 0 and n is the size of the array). Please correct me if I am wrong.
Can someone help me finding the time complexity?
@raghav6 You first need to build a recursive tree structure. From there you can judge the time complexity. You cannot judge the exact time complexity as for this problem it will totally depend on the values of coins available with you. But you can judge the worst case complexity looking at the tree.
For minimum coin changing problem, Lets say the value is 15 and the coins available are 1,7 and 10.
So recursive tree is somewhat like this:
Now the exact complexity would clearly be the total number of valid nodes that can be formed but you can see that it totally depends on the denominations of coins available with you.But looking at the tree you can say that each node can have maximum of 3 branches so the worst case complexity would be exponential with base 3. ie. 3^(something). So you can say time complexity is exponential.
For the memoized case or for the DP case, you can say that the complexity is O(mV) where m is the number of coins available with you and V is the target value. O(mV) since you need to fill a memo table/dp table of size m x V.
Hope this helps 
Hi! @pratyush63. Just saw your message, Thank you so much man! 
, I know building that recursive tree would have taken a lot of time and I am so thankful to you for always being there and clearing my doubts whenever I reach to you, I don’t know if you’re still working as a TA but even though you’re helping me whenever or wherever I get stuck! Thank you 
Means a lot to me.
1 Like
One more thing, in the Min Grid Cost Path Problem, is the time complexity O(2^n) can’t figure out what’s n here If I go exact it is approx O(2^(2n)) where n is the size of the row & col in the grid.
Have I used the right way to compute the time complexity? Here’s the picture.
Thank You 
@raghav6 Yes your approach is correct, complexity for the recursive approach would be O(2^n) , where n is the rows/columns in the grid.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.