Time complexity of below program

Question

can anyone pls tell me the time complexity of this func. this is for generating all valid parenthesis , given the count of pairs

Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]

My code is working fine, but im not sure about time complexity of it.

pls help

class Solution { public List generateParenthesis(int n) {

    HashMap<String,Boolean> hm = new HashMap<>();
   
    
    return  generate(hm,n);
    
  
}

public static List<String> generate(HashMap<String,Boolean> hm, int n ){
    
    if(n == 1){
        hm.put("()",true);
        List<String>temp = new ArrayList<>();
        temp.add("()");
        return temp;
    }
    
    List<String>temp = generate(hm,n-1);
    List<String>ans = new ArrayList<>();
    for(String pat : temp){
        for(int i = 0; i < pat.length(); i++){
            String newPat = pat.substring(0,i)+"()"+pat.substring(i);
            if(!hm.containsKey(newPat)){
                hm.put(newPat,true);
                ans.add(newPat);
            }
        }
    }
    
    
    return ans;
}

}

Answer 1

You have two for loops, which each run over m and n elements, it can be written as O(m*n), and be contracted to O(n^2) because m can be equal to n.

Answer 2

Your function is recursively calling itself, making time complexity analysis a bit harder.

Think about it this way: You generate all valid parenthesis of length n. It turns out that the number of all valid parenthesis of length n (taking your definition of n) is equal to the nth catalan number. Each string has length 2*n, So the time complexity is not a polynomial, but O(n*C(n)) where C(n) is the nth catalan number.

Edit: It seems like this question is already answered here.