Its Pretty Simple


#1

Initially it starts from (0,0) ,From here it has two moves

  1. either moves right
  2. or moves down

So, we may across the same position many times but here we across one position for one time .
This is because , before going to a position we check whether this is first time or not by checking MEM array i.e. if MEM[ i , j ] = -1 (first time) or else we have already reached it. So, total Position = R * C
Total Time=
T(0,0)+T(0,1)+T(0,2) +…T(0,C-1)+
T(1,0)+T(1,1)+T(1,2) +…T(1,C-1)+
.
.
.
.
T(R-1,0)+T(R-1,1)+T(R-1,2) +…T(R-1,C-1);
=O( R * C);