4 ms·

In the article n always refers to the length of the string.

• jonstewart 4y ago
  It does, but the article actually doesn't define n and it's confusing. In the common case, where s is short and the dictionary is big, the size of the dictionary probably matters most to the running time. s is likely a cache line and a handful of instructions to compare — whereas the dictionary probably doesn't fit in L1 or L2, maybe not L3. Obsessing about algorithmic analysis based on the string size instead of the size of the dictionary gives good signal for whether the candidate is a pedant, and poor signal about engineering.
• eesmith 4y ago
  Hmm. Yes, I misinterpreted this part: > 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.