Why is the time complexity of this algorithm exponential?

Question

During an interview, I was asked the time complexity of the following algorithm:

static bool SetContainsString(string searchString, HashSet<string> setOfStrings)
{
    for (int i = 0; i < searchString.Length; i++)
    {
        var segment = searchString.Substring(0, i + 1);

        if (setOfStrings.Contains(segment))
        {
            var remainingSegment = searchString.Substring(segment.Length);

            if (remainingSegment == "") return true;
            return SetContainsString(remainingSegment, setOfStrings);
        }
    }

    return false;
}

I answered "linear" because it appears to me to loop only through the length of searchString. Yes, it is recursive, but the recursive call is only on the portion of the string that has not yet been iterated over, so the end result number of iterations is the length of the string.

I was told by my interviewer that the time complexity in the worst case is exponential.

Can anyone help me clarify this? If I am wrong, I need to understand why.

Answer 1

I believe that your interviewer was incorrect here. Here’s how I’d argue why the time complexity isn’t exponential:

• Each call to the function either makes zero or one recursive call.
• Each recursive call reduces the length of the string by at least one.

This bounds the total number of recursive calls at O(n), where n is the length of the input string. Each individual recursive call does a polynomial amount of work, so the total work done is some polynomial.

I think the reason your interviewer was confused here is that the code given above - which I think is supposed to check if a string can be decomposed into one or more words - doesn’t work correctly in all cases. In particular, notice that the recursion works by always optimistically grabbing the first prefix it finds that’s a word and assuming that what it grabbed is the right way to split the word apart. But imagine you have a word like “applesauce.” If you pull off “a” and try to recursively form “pplesauce,” you’ll incorrectly report that the word isn’t a compound because theres no way to decompose “pplesauce.” To fix this, you’d need to change the recursive call to something like this:

if (SetContainsString(...)) return true;

This way, if you pick the wrong split, you’ll go on to check the other possible splits you can make. That variant on the code does take exponential time in the worst case because it can potentially revisit the same substrings multiple times, and I think that’s what the interviewer incorrectly thought you were doing.