python - Big Theta bound of 2 recursive calls -

given f(x, y) , g(n):

def f(x, y):     if x < 1 or y < 1:         return 1     return f(x - 1, y - 1) + f(x - 1, y - 1)  def g(n):     return f(n, n) 

what big theta bound of g(n)?

i reasoned since x == y, conditional in f(x, y) never true, 2 recursive calls determine complexity.

considering f(x - 1, y - 1): takes n recursive calls reach base case, each call branches f(x - 1, y - 1). @ point don't know how proceed.

(the answer Θ(2ⁿ).)

one way solve problem write recurrence relation problem. if you'll notice, arguments f equal 1 (you can see because start same in call g(n), , @ point equal). therefore, can write recurrence relation t(n) determines runtime of f(n, n).

so t(n) be? well, base case, t(0) 1, since function constant amount of work n drops 0. otherwise, function constant amount of work , makes 2 recursive calls problems of size n - 1. therefore, recurrence:

t(0) = 1

t(n+1) = 2t(n) + 1

looking @ terms of recurrence, see pattern:

• t(0) = 1
• t(1) = 3
• t(2) = 7
• t(3) = 15
• t(4) = 31
• ...
• t(n) = 2ⁿ⁺¹ - 1

you can formally prove using induction if you'd like. since t(n) given 2ⁿ⁺¹ - 1, runtime θ(2ⁿ).

hope helps!