Why is time complexity of Generate Parentheses O(4^n ( ​sqr root( n)))

Question

I am working on Leetcode Generate Parentheses here is the approach -

public class GenerateParentheses {

    public List<String> generateParenthesis(int n) {
        // Resultant list
        List<String> result = new ArrayList<>();
        /// Recursively generate parentheses
        generateParenthesis(result, "", 0, 0, n);
        return result;
    }

    private void generateParenthesis(List<String> result, String s, int open, int close, int n) {
        // Base case
        if (open == n && close == n) {
            result.add(s);
            return;
        }
        // If the number of open parentheses is less than the given n
        if (open < n) {
            generateParenthesis(result, s + "(", open + 1, close, n);
        }
        // If we need more close parentheses to balance
        if (close < open) {
            generateParenthesis(result, s + ")", open, close + 1, n);
        }
    }
}

I am understanding the solution from this website and it says the time complexity of this algorithm is O(4^n(​sqr_root(n))) because of nth Catalan number. Can someone simplify what that means and why is it's upper bound O(4^n(sqr_root(n)))?

Answer 1

According to Wiki:

C_n - The number of correct bracket sequences of length 2n, that is, such sequences of n left and n right brackets in which the number of opening brackets is equal to the number of closing brackets, and in any of its prefixes there are no fewer opening brackets than closing brackets.

Asymptotically, the Catalan numbers grow as (4^n)/(n^(3/2) * sqrt(pi)), which equals O(4^n / (n * sqrt(n)), but because we have to n of them, we got O(4^n / sqrt(n)) Time Complexity. One of the proofs of C_n Asymtotic. Proof with gen func also on Wiki.

UPD: There also useful answer about it