Time Complexity | Unmemoized | Minimum Score Triangulation of Polygon

I wanted to know what the unmemoized Time Complexity for the Minimum Score Triangulation of Polygon problem would be.

Code-

	int solve(int i, int j, vector<int> &values)
    {
        if(j-i+1 < 3) return 0;
        if(j-i+1 == 3) return values[i]*values[i+1]*values[i+2];
        int ans = INT_MAX;
        for(int k = i+1; k < j; k++)
        {
            ans = min(ans, solve(i,k,values) + values[i]*values[k]*values[j] + solve(k,j,values));
        }
        return ans;
    }

From what I can understand if we consider an interval of 'n' elements in the beginning then
T(n) = T(k) + T(n-k) for all k belongs to [1,n-1] where T(1)=T(2)=T(3)=1

How to find out the general time complexity of this problem

Also any resource on how to find the time complexity of such recursive solutions?

Comments (0)