1
$\begingroup$

I am not looking for the complexity of following algorithm but rather how to think about the problem and calculate complexity of a given solution?

One way is to perhaps use The Master Method for recursive functions, but that hides the "how?" part. I am trying to get much better at calculating complexities of algorithms on the fly.

Following is my solution for a problem which says that for an input text and a pattern, implement regular expression matching with support for '.' and '', where '.' matches a single character and '' matches none or more of the previous element.

var isMatch = function(text, pattern, mem=new Map()) {
    let key = text + '__' + pattern, pLen = pattern.length, 
        tLen = text.length, first_match;
    if (!mem.has(key)) {
        if (pLen === 0) { 
            mem.set(key, tLen === 0);
            return tLen === 0;
        }
        first_match = (tLen !== 0 && (pattern[0] == text[0] ||
                       pattern[0] == '.'));
        if (pLen >= 2 && pattern[1] == '*'){
            mem.set(key, (isMatch(text, pattern.substring(2), mem) ||
                    (first_match && isMatch(text.substring(1), pattern, mem))));
        } else {
            mem.set(key, first_match && isMatch(text.substring(1),
                    pattern.substring(1), mem));
        }
    }
    return mem.get(key);
};

My crude analysis so far:

From what I see here is that recursive calls to isMatch are the main contributor to overall time complexity. (Assuming that Map used for cacheing doesn't have very expensive operations). One set of isMatch calls is being called by taking a substring of given patter while the other set of calls to isMatch is being done by substring of given text.

So overall complexity should be describable in terms of length of pattern (p) and length of text (t) but I am not sure how to deduce the time complexity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.