Exchanging coin dp

#21

so anser would be 3*log(n) base 2 of memoizing it…

#22

yess…

#23

yes @shampblocks correct so it would be o(logn) after removing the constants

#24

@vatsal38 but in recursive approach is it right to replace 2 by 3 or 3 by 2 to get our approx time complexity??

#25

@shampblocks yes we can replace them in complexity and as you can see we have taken worst that is log base 2 n so its okay.
lot of round off are done in calculating time comp

#26

so i have calculated correct my approach is correct?? for both the approaches

#27

tell your final complexities for both ways

#28

for memoization recursive log(n) base 2 … for brute forces recursive its o(n)…

#29

yes its correct @shampblocks

1 Like
#30

ohk thanks sir…for clearing it…

#31

np just mark the doubt resolved :smiley:

1 Like
#32

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.