> I then push them on this until they realize that any implementation of the dictionary lookup function of a string would be o(n) at best, and as such the total runtime of the solution is O(n²).
I think the point is in the initial algorithm given there are (n-1) lookups of two substrings whose combined length is n, requiring the hash function to process (n-1)n characters, because the hash algorithm is O(n) in the query string length.
That said, the dictionary words have a finite size. The largest word in my /usr/share/dict/words is 24 characters - formaldehydesulphoxylate. That means for an input of size n only 24n bytes need to be processed to identify if it's composed of two dictionary words. And if it's 49 bytes long, or longer, it's a simple calculation - "not".
> I then push them on this until they realize that any implementation of the dictionary lookup function of a string would be o(n) at best, and as such the total runtime of the solution is O(n²).
I think the point is in the initial algorithm given there are (n-1) lookups of two substrings whose combined length is n, requiring the hash function to process (n-1)n characters, because the hash algorithm is O(n) in the query string length.
That said, the dictionary words have a finite size. The largest word in my /usr/share/dict/words is 24 characters - formaldehydesulphoxylate. That means for an input of size n only 24n bytes need to be processed to identify if it's composed of two dictionary words. And if it's 49 bytes long, or longer, it's a simple calculation - "not".
Under Big-O analysis, this is O(1) time.