I see, yes I think you do raise a very good point, but on the other hand, the issue could be quickly resolved by talking about it. Any good interviewer would s

I see, yes I think you do raise a very good point, but on the other hand, the issue could be quickly resolved by talking about it. Any good interviewer would say something like "Ah yes that's a very good point, I forgot to consider the implication of the English vocabulary. However, for the sake of this interview, let's assume the 'vocabulary' is made of strings that can be arbitrarily long. Does that change your answer?" After all, if we assume that all words are at most, say, 50 characters long, then there's no asymptotic complexity to speak of. Any string longer than 100 characters is trivially not a concatenation of two words.