Time Complexity Of Python Code For Finding The Longest Word That Can Be Made Of Other Words In The List

I am preparing for some coding interviews and came up with a solution to the following problem: 'Find longest word that can be made of other words in a list of words'. I have a ha

Solution 1:

Let n be the number of words in the list and m the length of the longest word.

The for-loop iterates over the words until valid_word returns true. The worst case would be, that non of the words can be concatenated from other words in the list. So this gives you a factor n.

valid_word iterates over all characters in a word and calls valid_pair which has the complexity O(f), where f = f(n,m) is the complexity of the in operator. (I don't know, how it is implemented). If for every character left is in words, but right is not, valid_word is called recursively m times, resulting in this formula:

T(m) = f + Σi=1,...m-1 T(m-i) < f + (m-1) ⋅ T(m-1) < m!⋅f 

So valid_word is in O(m!⋅f(n,m)) (this can be improved).

The over all complexity is O(n⋅m!⋅f(n,m) + n⋅log(n)). This is an upper bound, so maybe you can improve this, by showing that it is not possible to have an input that forces the algorithm to do all the steps.

But think of an input like this (withe spaces are only for better readability)

words = ['ab ac ad ae','ab ac ad af', ... , 'ab ac ad az',
         'ab ac ad', 'ab ac', 'ab']

Non of these words can be concatenated from the others, but the algorithm has to try many combinations. This examples can be improved and extended.