Calculate time complexity of nontrivial problems

Question

I am having trouble in calculating the time complexity of program shown below. It is a simple program to generate valid parentheses such as "((()))" "(()())" etc. However, I don't really know how to estimate time complexity for this kind of problems.

It will be appreciated if you can share some techniques you find useful here. It will be the best if you can analyze the program I linked as an example : )

My aim :

1. Estimate time complexity for nontrivial program. Typically a recursive program which has some pruning.

2. I am looking for a fast estimate solution, not a rigorous mathematical proving.

Thank you in advance.

The code in question:

public ArrayList<String> generateParenthesis(int n) {
    ArrayList<String> res = new ArrayList<String>();
    String oneSolu = "";

    Generate(n, n, res, oneSolu);

    return res;
}

private void Generate(int l, int r, ArrayList<String> res, String oneSolu) {
    if (l==0 && r==0) {
        res.add(oneSolu);
        return ;
    }

    //add left
    if (l > 0) {
        String t = oneSolu;
        t += "(";
        Generate(l-1, r, res, t);
    }

    if (r>l) {
        String t = oneSolu;
        t += ")";
        Generate(l, r-1, res, t);
    }
}

Answer 1

The number of valid parenthesis generated with n-pairs is nth catalan number which is defined as 2nCn/(n+1) but if u need more simplified bound then it is O(4^N) . More generally any recursive function is upper bounded by its max branching factor and depth as O(b^d) if work done at each level is O(1) so in this case depth = 2N and branching factor is approximately 2 hence T(n) = 2^(2N)=4^N.

Answer 2

I have to admit, your particular use case seems particularly tough, so don't be too hard on yourself.

1. Estimate time complexity for nontrivial program. Typically a recursive program which has some pruning.

2. I am looking for a fast estimate solution, not a rigorous mathematical proving.

I can give you my normal thought process when I'm analyzing runtimes. It won't be terribly helpful for this particular case, but can certainly be helpful in the general case (if you run into issues analyzing other programs later on).

I can't give any guarantees about not using rigorous math though; I tend to default to it if I want to be really sure of a bound. For loose bounds, the stuff is generally simple enough to where it's not a big issue though.

---

There's two main things that I generally try to think about first.

1) Can I at least write down the recurrence?

Some recurrences are familiar to a large number of people (like T(n) = T(n-1) + T(n-2)), while some have been studied pretty extensively (like anything solvable with the master method). If a program falls under this category, consider yourself pretty lucky.

In your particular case, the recurrence seems to be something like

T(L,R) = T(L-1,R) + T(L, R-1) if R > L
T(L,R) = T(L-1,R) otherwise, with base case
T(0,R) = R

Not the greatest start.

2) Analyzing how many times a particular function is called with specific arguments

This one is generally more useful in dynamic programming, where past results are stored to save computation, but is also another tool in the belt. That being said, this isn't an option if you can't compute how many times the function is called with specific arguments.

In this case though, this approach gets heavy on the math. The basic problem is that the number of times Generate() is called with a specific l and r depends entirely on the possible values of oneSolu. (The ArrayList is an accumulator, so that's not a worry)

In our case, we happen to know how long the string is (since the first call had l = r = n and each recursive call decreased exactly one of the two by 1), and we can also show that

1. For every value of oneSolu passed in, we can guarantee that every prefix has more (s than )s.
2. Every such string of this specific length is covered.

I'm pretty sure that value can be found, but 1) the math will get ugly very quickly and 2) even if you got that far, you then have to wrap it around a double summation and evaluate that too. Not practical, and even getting this far dealt with way more math than you wanted.

---

Now for the really coarse way to get an upper bound. This is the "quick" way, but it doesn't take into account any sort of pruning, so it can be pretty useless if you want a tight bound. It's already been posted, but I'll add it on anyway so that this answer sums up everything by itself.

3) Multiply the maximum depth by the max branching factor.

As already pointed out by @VikramBhat, you've got a branching factor of 2, and a maximum depth of 2n, so you're looking at a (very very) loose bound of 2²ⁿ = 4ⁿ total nodes, and as pointed out by @KarolyHorvath in the comments, the work per node is going to be linear, so that gives us a O(n4ⁿ) running time.