Grundy Number finding

#1

what is time complexity of finding grundy number
when min_coin = a and max_coin = b

#2

@sutharp777
The complexity is still linear with N being B

If your doubt is resolved please close it

#3

@Aarnav-Jindal-1059677350830863
How, but it looks like exponential.
At each state we are call all possible lower state.

#4

@sutharp777
Each state is only calculated once and then its result is stored
So it is not recalculated
Hence the complexity will end up begin linear

#5

@Aarnav-Jindal-1059677350830863
ok dp, than how linear it is O((b-a)n).

#6

@sutharp777
It will be O( b )

1 Like
#7

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.