0
def count(n):
    if n == 0 or n == 1:
        return 1
    else:
        sum = 0 
        left = 0        
        right = 0
        for x in range(1,n+1):
            left = count(x-1)
            right = count(n-x)
            sum +=  left * right
    return sum

I was reading this post and I wondered if no of different binary search trees from n nodes is

(2n)! / ((n+1)! * n!) from this post.

Then

  1. what will be the time complexity ? O(n!) ?
  2. what will be the recurrence relation ?
Community
  • 1
  • 1
c2h5oh
  • 227
  • 5
  • 9

1 Answers1

2

When you call count(n), it's calling each of count(0) to count(n-1) twice.

So I think you can write the recurrence like this:

T(n) = 2 * sum[T(0) upto T(n-1)] + nk where k represents the multiplication and summation part.

Now consider:

T(n+1) = 2 * sum[T(0) upto T(n)] + (n+1)k
       = 2 * sum[T(0) upto T(n-1)] + 2T(n) + nk + k
       = T(n) + 2T(n) + k
       = 3T(n) + O(1)

Solving this, it appears to be of O(3^n) complexity.

Worakarn Isaratham
  • 1,034
  • 1
  • 9
  • 16
  • If you're pointing to the growth of the Catalan number, that doesn't mean anything. The growth of the function itself and how you compute the values are two different matters. – Worakarn Isaratham Sep 29 '13 at 17:54