1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Have you tried looking up this sequence on OEIS? $\endgroup$ – Yuval Filmus Jun 29 at 18:34
  • $\begingroup$ What are the 22 combinations for n==3? $\endgroup$ – rici Jun 30 at 7:26
  • $\begingroup$ @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. $\endgroup$ – Jack Jun 30 at 9:57
  • $\begingroup$ @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)))." $\endgroup$ – Jack Jun 30 at 10:01
  • $\begingroup$ The asymptotic behavior of Catalan numbers is well-known. You can look it up, or find it yourself using Stirling's approximation. $\endgroup$ – Yuval Filmus Jun 30 at 10:21
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.