Why does grid traveller have a time complexity of 2^(n+m)?

Question

Grid Traveller

• Returns the number of ways to traverse from the top-left to the bottom-right corner of a n x m grid. An example of a recursive function would look like this

def grid_traveller(n,m):
    if n == 0 or m == 0: return 0
    if n == 1 and m == 1: return 1
    return grid_traveller(n-1,m), grid_traveller(n,m-1)

An example:

         2,2
       /     \
    1,2       2,1
   /   \      /  \
0,2     1,1  1,1  2,0

While I can come up with the solution I'm confused about the depth and time complexity. The depth is supposedly n+m because only either n or m can decrease at a time, so it will take n+m steps to reach (0,0). That sounds logical, but what does depth even mean? In this case, the tree has a height of 3 (instead of 2+2=4) and the number of recursion calls is 2 ((1,2) and (2,1)), so what does depth tell us? I used to think that depth = height of recursion tree (at least for a single input), but I'm not sure if I have the right idea.

I think if I understood a little more about depth I might figure out why the time complexity is 2^(n+m), but do feel free to explain on that too.

Answer 1

I was confused by a problem and it wasn't clear to me what I didn't understand. I think the thing that knocked me out of it was Ry-'s comment.

The complexity is the same even if the actual stack depth is different from the tree you’re analyzing by a constant offset.

When I posted this question I rejected the idea that height = n+m (along with some other self-confusion that I now have no idea why) but didn't notice the simple pattern that the examples I drafted all had height = n + m -1.

So now that I've re-accepted that depth = height of tree = n+m, I can go on to comfortably accept the time complexity. For completeness sake, here's my explanation:

Recursion depth is also known as the the height of the recursion tree. The time complexity is 2^(n+m) because for every level down the tree, the number of function calls we have to make doubles (1 -> 2 -> 4 -> 8 -> 16).

For a tree of height 3 (in this example), we have to make 2^3=8 calls (count the nodes above if you're confused!).
For a tree of height (n+m-1), we have to make 2^(n+m-1)~=2^(n+m) calls (because constants are insignificant when n+m approaches infinity).