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

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.

• Have you tried looking up this sequence on OEIS? – Yuval Filmus Jun 29 at 18:34
• What are the 22 combinations for n==3? – rici Jun 30 at 7:26
• @rici - Thanks for pointing this out. The results were incorrect. I'd copied and pasted the wrong column. I had another column with common sequences to compare with my results. I've updated my question. – Jack Jun 30 at 9:57
• @YuvalFilmus - Great advice. Using my now updated results (thanks @rici), results from OIES: oeis.org/… "Number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)); for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd)))." – Jack Jun 30 at 10:01
• The asymptotic behavior of Catalan numbers is well-known. You can look it up, or find it yourself using Stirling's approximation. – Yuval Filmus Jun 30 at 10:21

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.