R+C or min(R, C)


#1

Consider matrix 2x5, in this case at any given iteration the max number of function calls will be 2^2 = 4
so shouldn’t it be O(2^min(R, C)) ?


#2

The tree is a full binary tree, therefore there would be addition of m and n rather than the max.
How full binary tree? Because if you will see the tree closely, both parameters strive to reach m-1 and n-1 respectively, but at a time only one can be incremented. Thus in the most basic case, firstly first parameter will reach n-1, in n-1 iterations and then the second parameter will reach m-1, in m-1 iterations. Thus the total number of iterations would be n-1 + m-1 = n+m-2
Making the complexity O(2^(n+m))


#3

It isn’t a full binary tree, the strait path is R or C long, and the zigzag path is R+C - 2 long.

I suppose it must be some coefficient of 2^(R+C) - another term, which if that term is of a lower order than 2^(R+C) we can ignore it.

So it is 2^(R+C) but not because it is a full binary tree.