Search posts, tags, users, and pages
I'm not great at this, but I'd guess
2^min(R, C) = min(2^R, 2^C)
Also known as "not great"
If you'd add memoization
R * C
M Interestingly, the answer happens to be 2^( R + C ). And I can't fathom why.
I think for the complexity we can simplify it to
def f(r, c):
if r <= 0 or c <= 0:
return
f(r, c - 1)
f(r - 1, c)
f(R, C)
So the longest path to stop is R+C-1 if r=0 and c=1 or reverse. So 2^(R+C) would be the upper bound if all paths had the maximum length, I think.
But there are also quite some paths that stop earlier for small numbers (not sure if these play a bigger or smaller role for large R/C).
The ways to get a path that is R+C-1 could be seen as walking on a R x C grid from the left top to right bottom, stepping either down or right each time.
The 'correct' (pessimistic) paths are the ones with where out of R+C moves, exactly R are right. Anything else stops early and is thus shorter.
Total number of paths of length C+R is the total combinations, 2^(C+R).
Total number of paths of length C+R with R right turns is (C+R)!/(C!R!).
This ratio (C+R)!/(C!R!*2^(C+R)) goes down pretty slowly (although it does go to zero). I guess if most paths are close to the longest for large C and R then the pessimistic upper bound O(2^(R+C)) is fair.
There's surely a more mathematically rigorous way for this...
The memoization thing is easier. Starting at f(R, C), one sees that there is a path to any f(r, c) with 0 < r <= R and 0 < c <= C. That's a grid of C * R states. With memoization, they'd all be visited once (that's the idea of memoization). So O(R * C) seems right (and, I might add, immensely faster).
Mark You answer about the combination of all possible paths with R + C length is the one I was looking for. I got the clarity I was looking for. Thanks mate.
Mark I know the DP method would obviously work faster due to overlapping subproblems and optimal substructure, but the question demanded me to find the time complexity of the given code. Thanks for all the help. Do you happen to be a college student? Or a Post Graduate student?