Determining time complexity of recursive function

Question

I have written a recursive function which computes Catalan Numbers. The recursion formula is .

My code:

def catalan(n): # We call this function. To my opinion it is more elegant.
    d = dict()
    return catalan_rec(n,d)

def catalan_rec(n,d):
    if n == 0:
        result = 1
    elif n in d: return d[n]
    else:
        result = 0
        for i in range(n):
            result += catalan_rec(i,d)*catalan_rec(n-i-1,d)
        d[n] = result
    return result

Now, it is obvious that the recursion depth is O(n). I am not sure what is the time complexity of this algorithem. The recursion tree has O(n) nodes and in any node (except leaves) we make two calls. Any call is O(1) as we only check if we already have the result in the dictionary, hence the time complexity is O(n).

Is my reasoning correct?

And by the way, is there an option to write non recursive algorithm that runs in time complexity which is better than O(n^2)?

Thanks!

Answer 1

Not sure if this is what you want, but according to that page you could write the function to compute the catalan number in O(n) like this:

def catalan(n):
    num, div = 1, 1
    for x in range(n + 2, 2*n + 1):
        num *= x
    for x in range(2, n + 1):
        div *= x
    return num / div