What is the runtime of my recursive memoized solution-CodePudding

I am giving a binary search tree with n node with unique value 1 to n and need to compute how many structurally different binary search tree I can make from it. I use DFS with memoization to solve the problem. It is basically like if we have n node, the root node can be from 1 to n, then I recursively compute how many the subtree can the tree has. Also, I memoized the range of node value the tree can have and how many different tree can be made with that range of node value, so I dont recompute. I think the Time and Space are both O(n^2) as there can be n^2 different range for my tree node val. Can anyone comment on that?

class Solution {
    public int numTrees(int n) {
        
        // structrually unique BST with value from 1 to n
        // same structure but different number? no, one way to arrange node
        // from 1 to n start
        // left has num candid - 1 to 1
        // right has num candid   1 to n
        
        Map<Integer, Integer> memo = new HashMap<>();
        
        return numWays(1, n, memo);
    }
    
    
    private int numWays(int low, int high, Map<Integer, Integer> memo) {
        
        if(memo.containsKey(low * 100   high)) {
            return memo.get(low * 100   high);
        }
        
        if(low >= high) return 1;
        int ans = 0;
        for(int i = low; i <= high; i  ) {
            ans = ans   numWays(low, i - 1, memo) * numWays(i   1, high, memo);
        }
        memo.put(low * 100   high, ans);
        return ans;
    }
}

CodePudding user response：

The time complexity is currently O(n^3). It is true that there are only O(n^2) ranges, and at most O(n^2) pairs of (low, high) appearing as inputs to the numWays function. However, the numWays function takes O(high-low 1) steps after memoization, which is another O(n) factor.

To speed this up, you might notice that the number of BST's for [1,2,3,4] is the same as the number of BST's for [2,3,4,5] or for [3,4,5,6]; only the length of the array matters (giving you an O(n^2) algorithm from a tiny change). Another possible speedup comes from noticing that for every rooted binary tree with n nodes, there is exactly one way to label the nodes with [1,2,...,n] to get a BST, so you're looking for a way/recurrence to count rooted binary trees.

CodePudding user response：

We could also use a formula:

const f = n => n < 2 ? 1 : (4*n - 2) / (n   1) * f(n - 1);

for (let i=0; i<20; i  )
  console.log(f(i));