Why is the time complexity of this algorithm exponential?

Question

During the interview, I was given 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 seems to me that it only loops through the length of the searchString. Yes, it is recursive, but the recursive call refers only to that part of the string that has not yet been iterated, so the number of iterations of the final result is the length of the string.

My interviewer told me that the temporal complexity in the worst case is exponential.

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

Answer 1

, . Id , :

• , .
• .

O (n), n - . , .

, , , , , , , , , . , , , , , , , . , " ". "a" "pplesauce", , , theres "pplesauce". , - :

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

, , , . , , , , .