Exponential complexity of a program

Question

I got a program which depends on two entries of sizes m and n respectively. If T(m,n) is the running time of the problem, it follows:

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

for a given constant C.

I could prove that the time complexity is in Omega(2^min(m,n)). However, it seems that it is of complexity Omega(2^max(m,n)) (it was just confirmed to me) but I can't find a formal proof. Anyone has a trick?

Thanks in advance!

Answer 1

From the top of my head:
I assume the recursion of T(m,n) stops when you reach T(0,x) or T(x,0).

You have 3 factors contributing to the complexity:

1. Factor 1: T(m-1,n-1) decreases both m and n, so its lenght until m or n become 0 is min(m,n) steps (See note below)
2. Factor 2: T(m-1,n) decreases m only, so its length until m=0 is m steps.
3. Factor 3: T(m,n-1) same as above but until n=0 is n steps.

The overall complexity is the greater of all complexities, so it must be related to maximum of

max( min(m,n) steps, m steps, n steps) = max(m,n)
rather than min(m,n).

I guess you can fill in the details. The constant C does not contribute, or more precisely contributes with O(1), which is the lowest of all complexities here.

Note about item 1: This factor has also a branch for m-1 until 0 and n-1 until 0, so strictly speaking it s complexity will also be max(m,n)

Answer 2

First, you should define that, for all values of x, T(0, x) = T(x, 0) = 0 to have your recursion stop - or at least T(0, x) = T(x, 0) = C.

Second, "time complexity is in Omega(2^min(m,n))" must obviously be wrong. Set m=10000 and n=1. Now try to prove to me that the complexity is the same as m=1 and n=1. The T(m-1, n-1) and T(m, n-1) parts disappear quickly, but you still have to walk the T(m-1, n) part.

Third, this observation directly leads to 2^max(m, n). Try to find out the number of recursion steps for a few low values of m and n. Then try to make up a formula for the number of steps depending on m and n. (Hint: Fibonacci). When you have that formula, you're finished.