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!

Python is probably not the best language for implementing recursive algorithms, as it does not have proper recursion support. I believe that, under ideal circumstances, your reasoning is correct, but your actual run-times may not reflect this if you are using Python. I would suggest that you look at Haskell or R. — Kwarrtz
– Kwarrtz, Commented Aug 27, 2015 at 5:35
Kwarrtz, I'm aware of python's disadvantages, but I'm taking a course in university and they decided to teach python. It was a test question I tried to solve. By the way, in runs preety quick, not far slower than Haskell. — Galc127
– Galc127, Commented Aug 27, 2015 at 5:38
@Galc127 not any call is O(1). Notice, that you have for i in range(n) here. No way this would work in constant time :) — Konstantin
– Konstantin, Commented Aug 27, 2015 at 5:43
My suggestion was not out of consideration of performance (although I would have to see a benchmark to believe your claim), but rather for Python's fitness for running recursive algorithms. However, if the university course is in Python, you don't really have a choice. — Kwarrtz
– Kwarrtz, Commented Aug 27, 2015 at 5:44
@Galc127 The time is O(1) if either of the first two branches are followed. — Kwarrtz
– Kwarrtz, Commented Aug 27, 2015 at 5:45

Diego Basch · Accepted Answer · 2015-08-27 05:56:59Z

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

answered Aug 27, 2015 at 5:56

Diego Basch

13.1k2 gold badges31 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Determining time complexity of recursive function

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related