0

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);
    }
}
4
  • why is the right & left passed when it is not used Dec 29, 2013 at 17:17
  • I forgot to take it away..Never mind
    – Lamian
    Dec 29, 2013 at 18:01
  • @RobinGreen Yes, the code that the OP gave is in Java, but it sounds like what the OP is requesting is language agnostic. Dec 29, 2013 at 18:30
  • @DennisMeng OK, I guess most computer scientists should be able to read Java code. It's a fair point. Dec 29, 2013 at 18:31

2 Answers 2

1

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 22n = 4n 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(n4n) running time.

0

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.

13
  • 1
    Link to Catalan number wikipedia page Dec 29, 2013 at 18:23
  • 1
    I'm not quite sure this is correct. Yes, the matching parentheses task is a classic example of the usefulness of catalan numbers. However, both this and the depth analysis is only correct if you assume that each solution/node can be generated with O(1). I think here the string creation adds an O(N) multiplier. Let me think about it. Dec 29, 2013 at 18:32
  • @KarolyHorvath Yes u r right about it but in OP's case it is O(1) hence O(b^d) = O(4^N). Dec 29, 2013 at 18:39
  • nope, at the very least this is O(4^N * N), as you have 4^N solutions each with 2N length. And I think it's worse because of the many generated temporary strings. Dec 29, 2013 at 18:44
  • @KarolyHorvath I dunno so much about that second statement though. Sure, there's a lot of temporary strings, but there's at most a constant number created per node in the recursion tree. Dec 29, 2013 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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