What is the runtime of this algorithm? (Recursive Pascal's triangle)

Question

Given the following function:

Function f(n,m)
   if n == 0 or m == 0: return 1
   return f(n-1, m) + f(n, m-1)

What's the runtime compexity of f? I understand how to do it quick and dirty, but how to properly characterize it? Is it O(2^(m*n))?

Answer 1

This is an instance of Pascal's triangle: every element is the sum of the two elements just above it, the sides being all ones.

So f(n, m) = (n + m)! / (n! . m!).

Now to know the number of calls to f required to compute f(n, m), you can construct a modified Pascal's triangle: instead of the sum of the elements above, consider 1 + sum (the call itself plus the two recursive calls).

Draw the modified triangle and you will quickly convince yourself that this is exactly 2.f(n, m) - 1.

You can obtain the asymptotic behavior of the binomial coefficients from Stirling's approximation. http://en.wikipedia.org/wiki/Binomial_coefficient#Bounds_and_asymptotic_formulas

f(n, m) ~ (n + m)^(n + m) / (n^n . m^m)

Answer 2

The runtime of f(n, m) is in O(f(n, m)). This is easily verified by the following observation:

Function g(n, m):
    if n=0 or m=0: return 1
    return g(n-1, m) + g(n, m-1) + 1

The function f is called equally often as g. Furthermore, the function g is called exactly g(n, m) times to evaluate the result of g(n, m). Likewise, the function f is called exactly g(n, m) = 2*f(n, m)-1 times in order to evaluate the result of f(n, m).

As @Yves Daoust points out in his answer, f(n, m) = (n + m)!/(n!*m!), therefore you get a non-recursive runtime of O((n+m)!/(n!*m!)) for f.