How to calculate the time complexity of a recursive solution?-CodePudding

I am solving word break problem and I have used Dynamic Programming to optimise it, and the solution is working as well. But I am not able to calculate/figure out the time complexity of this approach.

Code:

class Solution {
public:
    int util(string &s, int i, unordered_set<string> &dict, vector<int> &DP) {
        if(i >= s.size()) {
            return 1;
        }
        if(DP[i] != -1) {
            return DP[i];
        }
        string next = "";
        for(int itr = i; itr < s.size(); itr  ) { // O(N)
            next  = s[itr];
            if(dict.find(next) != dict.end() and util(s, itr 1, dict, DP)) { // ?
                return DP[i] = 1;
            }
        }
        return DP[i] = 0;
    }
    
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        vector<int> DP(s.size()   1, -1);
        return util(s, 0, dict, DP);
    }
};

Could anyone please help me to understand the time complexity of the above algorithm step-by-step?

Thanks

CodePudding user response：

For each i ∈ [0..n) (n is length of s), your recursive function executes full inner loop exactly once (since the second time the result will be cached in DP).

At this point you might say that the whole algorithm is O(n²), but that is not true, there is a twist.

The inner loop which you labeled O(n) is not actually O(n), but O(n²), because you're searching next (substring of s) in the unordered_dict. Each such search takes O( next.length ) time, and, since length of next ranges from 0..length(s), the dict search is O(n), and the inner loop, consequently is O(n²).

Given all of the above, the whole algorithm is O(n³): O(n) from recursion and multiplied by O(n²) from inner loop.

Or, to be precise, O(n³ k), where k is the cummulative size of all strings in the wordDict (since you're constructing set from them).

P.S. To reduce complexity by factor of O(n) you can use Trie instead of unordered_set to store words from wordDict. With that your algorithm would be O(n² k).