How to find the Big-O for finding combinations of balanced parentheses?

Question

Given n pairs of parentheses, a function which returns the total number of all combinations well-formed parentheses could be:

def count_parenthesis(n, opened, closed):
  if closed == n:
    return 1

  num_pairs = 0

  if opened < n:
    num_pairs += _count_parenthesis(n, opened + 1, closed)

  if opened > closed:
    num_pairs += _count_parenthesis(n, opened, closed + 1)

  return num_pairs

Calling count_parentheses(3, 0, 0) results in the following call tree:

count_parenthesis(2, 0, 0)
  count_parenthesis(2, 1, 0) 
    count_parenthesis(2, 1, 1) 
      count_parenthesis(2, 2, 1)  
        count_parenthesis(2, 2, 2) 
  count_parenthesis(2, 2, 0) 
    count_parenthesis(2, 2, 1)  
      count_parenthesis(2, 2, 2)

How can the time and space complexity of this algorithm be determined?

There are a few areas which I'm unsure how to handle:

• The variable that moves towards the base case (closed == n) does not get incremented every time.

  • Calls where a brace is opened (opened + 1) do not directly move towards the base case.

• There isn't an obvious relationship (IMO) between n and the number of well-formed combinations:

n = 3, f(n) = 5
n = 4, f(n) = 14
n = 5, f(n) = 42
n = 6, f(n) = 132
n = 7, f(n) = 429
n = 8, f(n) = 1430

• I'm unsure how a recurrence relation can be defined when the base-case is not 1 or 0, but n?

• Should I approximate based on well-known runtime complexities? I.e. this looks like either exponential or factorial.

Note: I'm not looking for just an answer. I'd like to understand the process finding the time/space complexity for this type of recursive algorithm.

Answer 1

Let us start by analyzing the recursion tree of your algorithm. The depth is $2n$. As for the number of nodes, at level $k$ you have all arrangements of $a$ left parentheses and $k-a$ right parentheses such that $a \leq n$ and in each prefix of the word, there are at least as many left parentheses as right parentheses.

Bertrand's formula states that for each $a$, the number of such arrangements is $$ \frac{(a+1)-(k-a)}{k+1} \binom{k+1}{a+1} = \binom{k}{a} - \binom{k}{a+1}. $$ Hence the number of nodes at level $k$ is $$ \sum_{\lceil k/2 \rceil \leq a \leq \min(k,n)} \left[\binom{k}{a} - \binom{k}{a+1}\right] = \binom{k}{\lceil k/2 \rceil} - \binom{k}{\min(k,n)+1}. $$ Summing this for $k$ from $0$ to $2n$, we obtain $$ \sum_{k=0}^n \binom{k}{\lceil k/2 \rceil} + \sum_{k=n+1}^{2n} \left[\binom{k}{\lceil k/2 \rceil} - \binom{k}{n+1}\right]. $$ It follows from Stirling's approximation that this is $O(4^n/\sqrt{n})$, and conversely, just considering $k = 2n$ (corresponding to Catalan numbers), this is $\Omega(4^n/n^{1.5})$.

We are however not done, since the numbers involves are quite large — on the order of $n$ bits. Therefore arithmetic takes super-constant time. We still get a running time of $\tilde{O}(4^n)$.

Now for space complexity. The recursion tree is $n$ levels deep, and at each level we might be storing up to $n$ bits of information, giving an upper bound of $O(n^2)$ bits. This should be quite tight.