Take a look at this


Whatever be the nature of the problem (recursive or not) —> in the R x C grid, every cell while operated by the function calls its RIGHT and DOWN cells once.

That means for the first column and the first row elements the function is called ONCE. The remaining elements (R-1) x (C-1) grid are called TWICE (once by their left cell and once by the cell above).

Then finally 1 row and 1 column outside the array bounds is also called.

This gives a total no. of calls of: (R + C - 1) + 2 * (R-1)(C-1) + (R + C + 1)
Giving: 2RC + 2 calls exactly
Therefore O(R

What’s going wrong??


Think about the last cell in the grid. i.e the right-bottom corner. That element will definitely be called more than twice because you can come up with more than two paths from the left-top cell (by just going DOWN or RIGHT) to reach that cell.