Time Complexity(Rat in a Maze)

#1

i want a clear idea of what and how the time complexity for this algorithm

#2

Hi @dare_devil_007, first let us understand all aspects related to problem,
considering a grid of size MxN, and rat has to move from 0,0 to M-1,N-1 (some cells may be blocked and rat can move either down or right)
Now at every point rat has two choices, go down or go left and to reach destination, rat has to make (M+N) moves, so total recursion complexity turns out as O(2^(M+N)) which is very high, but there are many overlapping recursive calls, so using DP reduces the complexity to O(MN).

#3

when there are two choices at every point ,then for a particular row it should be 2^m and it is for all rows then it has to be n*2^m right?

#4

@dare_devil_007 No, rat don’t travel all cells!, it only travels n+m cells

1 Like