What is the complexity of my solution?


  • 0
    C

    When I saw this question, I found a solution for this in a minute. And here is my solution:

    int numTrees(int n) {
            if(n == 0)  return 1;
            if(n == 1)  return 1;
            if(n == 2)  return 2;
            int result = 0;
            for(int i = 0 ; i < n ; i++)
            {
                result += (numTrees(i) * numTrees(n-i-1));
                
            }
            return result;
        }
    

    But apparently, the time complexity is way too big. I am not sure how to estimate the complexity here, could anyone give me some hints for this? Thanks.

    Also, I improve this method by using an array to store the numbers needed to calculate the result. I think for this one which is accepted, the time complexity is O(n) since it has to set up the array first. But the space complexity is also O(n), am I correct?

    vector<int> temp_arr;
    
    int numTrees(int n) {
        if(n == 0)  return 1;
        if(n == 1)  return 1;
        if(n == 2)  return 2;
        temp_arr.resize(n+1);
        temp_arr[0] = 1;  // n == 0
        temp_arr[1] = 1;  // n == 1
        temp_arr[2] = 2;  // n == 2
        
        for(int i = 3 ; i <= n ; i++)
        {
            helper(i);
        }
        
        return temp_arr[n];
    }
    
    int helper(int x) {
        int result = 0;
        for(int i = 0 ; i < x ; i++)
        {
            result += (temp_arr[i] * temp_arr[x-i-1]);
            
        }
        temp_arr[x] = result;
        return result;
    }

  • 1
    O

    Hi, I'm not a CS guru, so I'll follow this thread for further answers.

    Anyway, I'll try to explain some parts.

    I doubt you first answer can be accepted, because it has very high both time and space complexity. The problem is during recursion, it doesn't save previously computed results. Say, you want to calculate numTrees(10). You have to compute numTrees(0)*numTrees(9) and numTrees(9)*numTrees(0) with same time complexity! However, since you have already calculated numTrees(9) before, it is no need to calculate it again.
    Besides, this recursion makes the stack grow really fast. I conjure the space complexity should be above O(2^N) but not sure.

    The second is way much better. Actually its's almost the same as most voted answer in the discussion forum. Since you use an array to store previously calculated answers, the space complexity is O(N). For the time complexity, it is Sum_i_0_n(Sum_j_0_i) which is easily to prove to be O(N^2).

    Hope this helps you.

    Pufan


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.