Time complexity for combination of parentheses

Question

I tried to do the classical problem to implement an algorithm to print all valid combinations of n pairs of parentheses.

I found this program (which works perfectly) :

public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
    if (leftRem < 0 || rightRem < leftRem) return; // invalid state

    if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
        String s = String.copyValueOf(str);
        list.add(s);
    } else {
        if (leftRem > 0) { // try a left paren, if there are some available
            str[count] = '(';
            addParen(list, leftRem - 1, rightRem, str, count + 1);
        }
        if (rightRem > leftRem) { // try a right paren, if there’s a matching left
            str[count] = ')';
            addParen(list, leftRem, rightRem - 1, str, count + 1);
        }
    }
}

public static ArrayList<String> generateParens(int count) {
    char[] str = new char[count*2];
    ArrayList<String> list = new ArrayList<String>();
    addParen(list, count, count, str, 0);
    return list;
}

As I understand, the idea is that we will add left brackets whenever possible. For a right bracket, we will add it only if the remaining number of right brackets is greater than the left one. If we had used all the left and right parentheses, we will add the new combination to the result. We can be sure that there will not be any duplicate constructed string.

For me, this recursion, is like when we work with a tree for example and we do the pre order traversal for example : we go to a left node EACH time is possible, if not we go right, and then we try to go left just after this step. If we can’t, we "come back" and go right and we repeat the traversal. In my opinion, it's exactly the same idea here.

So, naively, I thought that the time complexity will be something like O(log(n)), O(n.log(n)) or something like that with logarithm. But, when I tried to search about that, I found something called "number of CATALAN", which we can use to count the number of combination of parentheses....(https://anonymouscoders.wordpress.com/2015/07/20/its-all-about-catalan/)

What are the time complexity in your opinion? Can we apply the master theorem here or not?

Answer 1

The complexity of this code is O(n * Cat(n)) where Cat(n) is the nth Catalan number. There are Cat(n) possible valid strings that are valid combinations of parenthesis (see https://en.wikipedia.org/wiki/Catalan_number), and for each a string of length n is created.

Since Cat(n) = choose(2n, n) / (n + 1), O(n * Cat(n)) = O(choose(2n, n)) = O(4^n / sqrt(n)) (see https://en.wikipedia.org/wiki/Central_binomial_coefficient).

There's two main flaws with your reasoning. The first is that the search tree is not balanced: the tree that you search when you close the right brace is not the same size as the tree you search when you add another left brace, so more common methods for computing complexity don't work. A second mistake is that even if you assume the tree is balanced, the height of the search tree would be n, and the number of leaves found O(2^n). This differs from analysis of a binary search tree, where you usually have n things in the tree and the height is O(log n).

I don't think there's any standard way to compute the time complexity here -- ultimately you're going to be reproducing something like the math done when you count valid parenthetical strings -- and the Master theorem isn't going to power you through that.

But there is a useful insight here: if a program generates f(n) things, and the cost of generating each if c(n), then the program's complexity can't be better than O(c(n)f(n)). Here, f(n) = Cat(n) and c(n) = 2n, so you can quickly get a lower bound for the complexity even if analyzing the code is difficult. This trick would have immediately led you to discard the idea that the complexity is O(log n) or O(n log n).