algorithm - Exponential complexity of a program -

I have found a program which depends on two entries of m and n respectively I if T (M, N) problem If it is time to walk, then it is as follows:

T (m, n) = T (m-1, n-1) + t (m-1, n) + t (m, n -1) + C

A fixed constant c.

I can prove that the complexity of time is in Omega (2 ^ min (m, n))). However, it seems that this complexity is Omega (2 ^ max (M, N)) (it was confirmed only for me), but I can not find a formal proof. Anyone have a trick?

Thanks in advance!

Head over me: when I reach T (0, X) or T (X, 0) Prevent T (M, N) recycling.

You have 3 factors that contribute to complexity:

1. Factor 1: T (M-1, N-1) M and N decreases both, so Minimum (M, N) phase (see note below)
2. Factor 2: T (M-1, N) only decreases the meter, so its length is equal to m = 0 m The step I is 3: T (M, N-1) is similar to the above, but until n = 0 n does not move.

The overall complexity is greater than all the complexities, so the maximum

  maximum (minimum (m, n) phase, m Phase, n phase) = Maximum (M, N).  

I think you can fill in the details. Continuous C does not contribute with O (1), or makes more precise contributions, which is the lowest of all the complications here.

Note about item 1: In this case, there is also a branch of M-0 to 0 and N to 1 to 0, so strictly its complexity is also maximized (M, N)